Path Sum

The problem asks for determining whether there exists a root-to-leaf path in a binary tree such that the sum of all the values along the path equals a given target sum. We can solve this problem using recursion.

Here’s the approach:

  1. Base Case: If the current node is None, return False. It means we have reached a dead end.
  2. Leaf Node Check: If the current node is a leaf node (both left and right children are None), we check if the value of the current node equals the remaining target sum. If it does, return True.
  3. Recursive Calls: Recursively call the function for the left and right children, subtracting the value of the current node from the target sum.
  4. Result: If either of the recursive calls returns True, it means a valid path has been found, and we return True. If both return False, then there’s no valid path for the current subtree, and we return False.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # Base case: If node is None, return False
        if not root:
            return False

        # Subtract the value of the current node from target sum
        targetSum -= root.val

        # If current node is a leaf, check if target sum is 0
        if not root.left and not root.right:
            return targetSum == 0

        # Recursively call for left and right children
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

Key Insights:

  • The approach follows the Depth-First Search (DFS) pattern.
  • 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.
 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

# 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} sum
# @return {Boolean}
def has_path_sum(root, sum)
  # Base case
  if root.nil?
      return false
  end
  
  # Unit of work  
  sum -= root.val
  # Did we hit the leaf node? If so check if the path sum is equal to the given sum       
  if (root.left.nil? && root.right.nil?)
      return sum == 0
  end
  
  # Check the left and right subtrees  
  has_path_sum(root.left, sum) || has_path_sum(root.right, sum)
end

Solution Outline

  1. Recursive Approach

  2. Start at the root

  3. Keep decrementing the path sum

  4. If we reach 0 when we get to the leaf node

  5. Return true

  6. If you never reach 0 for any leaf nodes

  7. Return false

  8. What is the base case?

    • What is the smallest instance of the problem?
    • If the root is null, return false

  9. What is the unit of work?

    • Repeating work at each recursive call (what do we do?) After the base case, check if we have reached the leaf node Check for the condition

  10. We need to perform the unit of work before the recursive call.

  11. We need to make two recursive calls.

  12. True or False is returned from the recursive function 6 If left-subtree || right-subtree return it

5-4-11-7 = 27 It exceeeds. The left subtree in this case will return false 5-4-11-2 = 22 We succeed. The right subtree in this case will return true

 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

# 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} sum
# @return {Boolean}
def has_path_sum(root, sum)
    # Base case: empty tree
    # Minimize the number of base cases     
    if root.nil?
        return false
    end
    # Unit of work
    sum -= root.val

#    Check if we are the leaf node
    if (root.left.nil? && root.right.nil?)
        return sum == 0
    end
#     Check both left and right subtrees
    has_path_sum(root.left, sum) || has_path_sum(root.right, sum)
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

# 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} sum
# @return {Boolean}
def has_path_sum(root, sum)
  # Base case
  if root.nil?
      return false
  end
  stack = [[root, sum - root.val]]
  
    while !stack.empty?
       node, current_sum = stack.pop

        if node.left.nil? and node.right.nil? and current_sum == 0
            return true
        end
        if node.right
            stack << [node.right, current_sum - node.right.val]
        end
        if node.left
            stack << [node.left, current_sum - node.left.val]
        end
    end
   return false
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

# 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} sum
# @return {Boolean}

1. How do we make the transition from recursive to iterative?

   Differences
    - You have to manage the stack programmatically in iterative version
    - You have to manage the state programmatically in iterative version
    
    Similarities
    - Base case => Edge case
    - When we reach the leaf node, we check
    - Unit of work
    
2. We have to maintain the state as we traverse this tree.
    
3. We have to traverse, if we have a right child, if so push it on to the stack
   if we have a left child, if so push it on to the stack
   
4. When do we return true and when do we return false
    As soon as we find the path sum == sum, return true (early termination)
    When we have explored all the paths and we have not found any path that
    adds up to the sum, we return false (outside the loop)

5. How do we keep track of the running sum?
    - We have add it as a pair to the stack

[5, 17]
[]

[8, 9]
[4, 13]

4, 13


[8, 9]

2, 0

=end

def has_path_sum(root, sum)
    if root.nil?
        return false
    end
    
    stack = [[root, sum - root.val]]
    
    while !stack.empty?
        node, current_sum = stack.pop
        
        if node.left.nil? and node.right.nil? and current_sum == 0
            return true
        end
        
        if node.right
            stack << [node.right, current_sum - node.right.val]
        end
        if node.left
            stack << [node.left, current_sum - node.left.val]
        end
    end
    
    return false
end

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} sum

@return {Boolean}

=begin

  1. How do we make the transition from recursive to iterative?

    Differences

    • You have to manage the stack programmatically in iterative version
    • You have to manage the state programmatically in iterative version

    Similarities

    • Base case => Edge case
    • When we reach the leaf node, we check
    • Unit of work

  2. We have to maintain the state as we traverse this tree.

  3. We have to traverse, if we have a right child, if so push it on to the stack if we have a left child, if so push it on to the stack

  4. When do we return true and when do we return false As soon as we find the path sum == sum, return true (early termination) When we have explored all the paths and we have not found any path that adds up to the sum, we return false (outside the loop)

  5. How do we keep track of the running sum?

    • We have add it as a pair to the stack

[5, 17] []

[8, 9] [4, 13]

4, 13

[8, 9]

2, 0

=end

def has_path_sum(root, sum) if root.nil? return false end

stack = [[root, sum - root.val]]

while !stack.empty?
    node, current_sum = stack.pop
    
    if node.left.nil? and node.right.nil? and current_sum == 0
        return true
    end
    
    if node.left
        stack << [node.left, current_sum - node.left.val]
    end
    if node.right
        stack << [node.right, current_sum - node.right.val]
    end
end

return false

end

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 {Boolean}

def has_path_sum(root, sum)

Base case

if root.nil? return false end

Unit of work

sum -= root.val

Did we hit the leaf node? If so check if the path sum is equal to the given sum

if (root.left.nil? && root.right.nil?) return sum == 0 end

Check the left and right subtrees

has_path_sum(root.left, sum) || has_path_sum(root.right, sum) end

“112. Path Sum” is about determining if a binary tree has a root-to-leaf path such that adding up all the values along the path equals a given target sum.

An isomorphic problem to this could be “437. Path Sum III”. In the “Path Sum III” problem, you are asked to find the number of paths in a binary tree that the sum of the nodes in the path equals a given target sum. The path does not need to start at the root and end at a leaf, but it must move downwards (traveling only from parent nodes to child nodes).

While the “Path Sum III” problem is more generalized, both problems fundamentally require us to find paths in a binary tree based on the sum of the nodes. Both require the use of depth-first search or a similar tree traversal technique to explore all possible paths in the tree. The main difference is that “Path Sum” requires the path to start at the root and end at a leaf, while “Path Sum III” allows for paths to start and end anywhere. However, the techniques used to solve both problems are similar, making them isomorphic at a structural level.

1
2
3
4
5
6

def hasPathSum(self, root: TreeNode, sum: int) -> bool:
	if not root:
		return False
	if not root.left and not root.right and root.val == sum:
		return True
	return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

Problem Classification

  1. Binary Trees: This problem centers around a binary tree, which is a type of data structure in which each node has at most two children, referred to as the left child and the right child.

  2. Tree Traversal: The problem requires understanding of how to traverse a tree, visiting each node in a specific order. In this case, we need to traverse all paths from root to leaves.

  3. Recursion: The problem requires knowledge of recursion, as the solution involves a function calling itself to explore all possible paths in the tree.

  4. Path Sum: This problem involves the concept of a “path sum” in a tree, where the sum is the total of node values along a path from root to leaf.

  5. Decision Making: This problem also involves decision making since you have to make a decision at each node, either go to the left or right child, or end the path if the sum is found or the node is a leaf node.

Language Agnostic Coding Drills

  1. Understanding Binary Trees: This problem involves binary trees. A good understanding of how they work is the first key step.

  2. Recursive Functions: The solution involves recursion, as it dives deeper into each level of the tree.

  3. Path Sum in Trees: The problem involves finding a path from root to leaf that sums to a specific target.

Targeted Drills in Python

  1. Understanding Binary Trees:
1
2
3
4
5

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
  1. Recursive Functions:
1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # prints 120
  1. Path Sum in Trees:

Here, we can introduce the concept of finding a path sum in a binary tree. This drill will involve building a tree, and then writing a recursive function to sum up the values of nodes in a path from root to leaf. We can begin by finding the sum of the path to the leftmost leaf, and then generalize to find all path sums, which will prepare us for the final problem:

1
2
3
4
5

class Solution:
    def pathSum(self, root):
        if not root:
            return 0
        return root.val + self.pathSum(root.left)

From here, we would need to modify the function to check if the path sum is equal to a given target, which would lead directly to the solution of the original problem.