algoadvance

You are given the root of a binary tree and an integer targetSum. Return all root-to-leaf paths where each path’s sum equals targetSum. A leaf is a node with no children.

Example:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Clarifying Questions

1. What is the maximum height of the binary tree?
   • This affects the potential depth of the recursion.
2. What should be done if the root is null?
   • An empty tree should return an empty list.
3. What should be done if no paths meet the targetSum?
   • Return an empty list.

Strategy

1. Depth-First Search (DFS): Use DFS to traverse all paths from the root to leaves.
2. Backtracking: Use a list to store the current path and backtrack once a leaf is reached or a wrong path is detected.
3. Path Sum Calculation: Keep track of the current sum as we traverse the tree. If a leaf is reached and its path sum equals targetSum, append the path to the result list.

Code

from typing import List, Optional

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

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    def dfs(node, current_path, current_sum):
        if not node:
            return
        
        # Include the current node to the path
        current_path.append(node.val)
        current_sum += node.val
        
        # Check if it's a leaf
        if not node.left and not node.right and current_sum == targetSum:
            result.append(list(current_path))
        else:
            # Continue DFS on left and right subtrees
            dfs(node.left, current_path, current_sum)
            dfs(node.right, current_path, current_sum)
        
        # Backtrack: remove the current node from the path
        current_path.pop()
    
    result = []
    dfs(root, [], 0)
    return result

Time Complexity

• Time Complexity: (O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal.
• Space Complexity: (O(N)) due to the recursion stack and the space needed for storing the current path for each node until backtracking. In the worst case, the binary tree could be a linked list, increasing the stack depth to (N).

This solution ensures that we explore every path from the root to the leaf and check if the path sum equals the targetSum. Each potential path is considered exactly once, leading to an efficient and clear implementation.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?