Path Sum II - Solution
Solutions and explanations
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
path = []
def find_paths(node, remaining_sum):
if not node:
return
path.append(node.val)
if not node.left and not node.right and node.val == remaining_sum:
res.append(path.copy())
else:
find_paths(node.left, remaining_sum - node.val)
find_paths(node.right, remaining_sum - node.val)
path.pop() # Undo path change
find_paths(root, targetSum)
return res
Complexity Analysis
Here, n is the total number of nodes, l is the number of leaf nodes, and h is the height of the binary tree.
-
Time Complexity:
O(n + l * h)- Traversal Time: Each node is visited once during traversal which contributes
O(n)time. - Path Copying Time: For each leaf node, if the path sum matches the target, then we copy the path of length atmost
hto the result. So, the total copying time isO(l * h).
Note:
- We only undo the current root-to-leaf path as the DFS retreats. This does not increase the time complexity, because each node’s value is added to the path exactly once and removed exactly once, resulting in only constant extra work per node.
- Traversal Time: Each node is visited once during traversal which contributes
-
Space Complexity:
O(h + l * h)-
Output space:
O(l * h)— to store all valid root-to-leaf paths. Each leaf node can contribute a valid path, and each path can be up to lengthh. So, output takesl * hspace in worst case. -
Recursion Stack:
O(h)— one stack frame per level of the tree. -
Temporary path list:
O(h)— a single list that holds the current root-to-leaf path, with at mosthvalues at any time. And the same temporary list is reused for all the recursive calls, and only the final valid paths are copied into the result.
-