Path Sum II

The problem is about finding all root-to-leaf paths in a binary tree where the sum of the node values in the path equals a given target sum. Here’s an approach to solve this problem:

Initialization: Create a list paths to store the final paths and a temporary list current_path to keep track of the current path.
Base Case: If the root is None, return an empty list.
Recursion: Use a recursive function to traverse the tree in a Depth-First Search manner, exploring the paths.
Path Handling: At each node, add its value to current_path and subtract its value from targetSum. If it’s a leaf node and the updated targetSum equals 0, add current_path to paths.
Backtracking: After processing the current node, backtrack by removing the last element from current_path.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        paths = []

        def dfs(node, current_path, remaining_sum):
            if not node:
                return

            # Add current node value to path
            current_path.append(node.val)

            # Subtract node value from remaining sum
            remaining_sum -= node.val

            # If it's a leaf node and remaining sum is 0, add path to result
            if not node.left and not node.right and remaining_sum == 0:
                paths.append(list(current_path))

            # Recursive call for left and right children
            dfs(node.left, current_path, remaining_sum)
            dfs(node.right, current_path, remaining_sum)

            # Backtrack
            current_path.pop()

        dfs(root, [], targetSum)
        return paths

Key Insights:

The approach follows the Depth-First Search (DFS) pattern with backtracking.
The time complexity is (O(n)), where (n) is the number of nodes in the tree since we visit each node once.
The space complexity is (O(\log n)) for a balanced tree or (O(n)) for a skewed tree, due to the recursion stack and the space needed to store the paths.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def dfs(node, current_sum, candidate, output)
    if node.nil?
        return
    end

    candidate << node.val

    if current_sum == node.val && node.left.nil? && node.right.nil? 
        output << candidate.dup
    else
        dfs(node.left, current_sum - node.val, candidate, output)
        dfs(node.right, current_sum - node.val, candidate, output)
    end
    candidate.pop
end

# @param {TreeNode} root
# @param {Integer} target_sum
# @return {Integer[][]}
def path_sum(root, target_sum)
    candidate = []
    output = []
    current_sum = 0
    dfs(root, target_sum, candidate, output)
    output
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @param {Integer} target_sum
# @return {Integer[][]}
def wrapper(node, target, candidate, output)
  if node.nil?
    return
  end

  target -= node.val
  candidate << node.val
  
  if node.left.nil? && node.right.nil?
    if target == 0
      output << candidate.dup
    end
  else
    wrapper(node.left, target, candidate, output)
    wrapper(node.right, target, candidate, output)    
  end

  candidate.pop
end

def path_sum(root, target_sum)  
  output = []
  candidate = []
  wrapper(root, target_sum, candidate, output)
  output   
end

layout: post title: Path Sum II excerpt: tags: top-to-bottom-processing

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Solution

The direction in which we need to process the nodes are from top to bottom. This means we are going to provide some parameters in the recursive wrapper method that will keep track of the state as we traverse down the tree.

In this problem, the potential solution is constructed in the candidate parameter. The current_sum keeps track of the remaining amount we need to satisfy the given sum. The output parameter collects all the solutions.

Definition for a binary tree node:

1
2
3
4
5
6
7
8
class TreeNode
   attr_accessor :val, :left, :right
   def initialize(val = 0, left = nil, right = nil)
       @val = val
       @left = left
       @right = right
   end
end

The wrapper method for traversing the tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def dfs(node, current_sum, candidate, output)
  if node.nil?
    return
  end
    
  candidate << node.val
    
  if current_sum == node.val && node.left.nil? && node.right.nil? 
    output << candidate.dup
  else
    dfs(node.left, current_sum - node.val, candidate, output)
    dfs(node.right, current_sum - node.val, candidate, output)
  end
  
  candidate.pop
end

# @param {TreeNode} root
# @param {Integer} target_sum
# @return {Integer[][]}
def path_sum(root, target_sum)
  candidate = []
  output = []
  current_sum = 0
  
  dfs(root, target_sum, candidate, output)
  
  output
end

The problem naturally maps to the DFS traversal for searching all the solutions to the problem.

Complexity Analysis

Time Complexity

O(N2) where N is the number of nodes in a tree. In the worst case, we could have a complete binary tree, then there would be N/2 leafs. For every leaf, we perform a O(N) operation of copying over the nodes to a new list to be added to the final result. Hence, the complexity in the worst case could be O(N2).

Space Complexity

O(N) - The new lists that we create for the paths are part of the output. The only additional space that we use is the result list to keep track of nodes along a branch.

Refactored Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def wrapper(node, target, candidate, output)
  if node.nil?
    return
  end
    
  target -= node.val
  candidate << node.val
  
  if node.left.nil? && node.right.nil?
    if target == 0
      output << candidate.dup
    end
  else
    wrapper(node.left, target, candidate, output)
    wrapper(node.right, target, candidate, output)    
  end

  candidate.pop
end

def path_sum(root, target_sum)  
  output = []
  candidate = []
  
  wrapper(root, target_sum, candidate, output)
  
  output   
end