Tree Path - Find All Root-to-Leaf Paths Summing to a Target

Question

## Problem

Given the root of a binary tree and a target integer `k`, return all root-to-leaf paths where the sum of node values equals `k`. Each path is a list of node values from root to leaf.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def path_sum(root: TreeNode, k: int) -> List[List[int]]:
    ...
```

**Example:**
```
Tree:
        5
       / \
      4   8
     /   / \
    11  13   4
   /  \      \
  7    2      1

path_sum(root, 22) -> [[5,4,11,2], [5,8,4,5]]
# Wait - no "5" child; path_sum(root, 22) -> [[5,4,11,2]]
```

## Follow-ups

1. Modify to return the maximum sum path (not necessarily root-to-leaf - any path allowed).
2. How does the solution change for an N-ary tree?
3. How would you count the number of paths (not just root-to-leaf) summing to `k`? What data structure helps?
4. Handle negative node values - does your current solution still work?

Tree Path - Find All Root-to-Leaf Paths Summing to a Target

Question Details

Full Details

Topics

More from C3 AI