Path Sum II All Paths

Return every root-to-leaf path whose node values sum to a target integer.

binary-tree dfs backtracking path-sum

You are given a binary tree where each node is a dictionary with keys `val`, `left`, `right`. The `val` key holds an integer, and `left` and `right` are either `None` or another dictionary of the same shape. Implement the function `path_sum_all(root, target_sum)` that returns a list of all root-to-leaf paths (each path as a list of node values) such that the sum of the values along the path equals `target_sum`. A leaf is a node whose `left` and `right` are both `None`. If there are no valid paths, return an empty list. The order of paths in the result does not matter. For an empty tree (root is `None`), return an empty list. The trees are represented as nested dictionaries, not custom objects.

Constraints

The number of nodes is between 0 and 2000. Node values and target_sum are integers in the range [-1000, 1000]. The depth of the tree can be up to 1000. The solution should run in O(N) time and O(N) space, where N is the number of nodes.

Example

```python
# Construct the tree:
#       5
#      / \
#     4   8
#    /   / \
#   11  13  4
#  /  \    / \
# 7    2  5   1
#
# Represented as:
# root = {
#   'val': 5,
#   'left': {'val': 4, 'left': {'val': 11, 'left': {'val': 7, 'left': None, 'right': None}, 'right': {'val': 2, 'left': None, 'right': None}}, 'right': None},
#   'right': {'val': 8, 'left': {'val': 13, 'left': None, 'right': None}, 'right': {'val': 4, 'left': {'val': 5, 'left': None, 'right': None}, 'right': {'val': 1, 'left': None, 'right': None}}}
# }
#
# path_sum_all(root, 22) -> [[5, 4, 11, 2], [5, 8, 4, 5]]
```

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use depth-first search to traverse the tree, keeping track of the current path and the remaining sum.

When you reach a leaf, check if the remaining sum equals the leaf's value; if so, add the path to the result.

Remember to backtrack by removing the last node after exploring both children.

For an empty tree, return an empty list.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.