Problem Description

You're given a binary tree and a target sum. Your task is to determine if there exists a path from the root to any leaf node where the sum of all node values along that path equals the target sum.

A root-to-leaf path means starting from the root node and following edges down to a leaf node (a node with no children). You need to add up all the values of nodes along this path and check if the total equals targetSum.

For example, if you have a tree with root value 5, and a path goes 5 → 4 → 11 → 2 (where 2 is a leaf), the path sum would be 5 + 4 + 11 + 2 = 22. If targetSum is 22, you would return true.

The solution uses a depth-first search (DFS) approach. It recursively traverses the tree while keeping track of the cumulative sum from the root to the current node. The function:

1. Starts from the root with an initial sum of 0
2. At each node, adds the node's value to the running sum
3. When reaching a leaf node (both left and right children are None), checks if the accumulated sum equals the target
4. Returns true if any root-to-leaf path sum matches the target, false otherwise

The recursion explores both left and right subtrees using the logical OR operator, meaning if either subtree contains a valid path, the result is true.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to traverse from root to leaf nodes.

DFS

• We arrive at DFS: Since we're dealing with a tree and need to explore paths from root to leaf, DFS is the appropriate choice.

Why DFS is suitable for this problem:

• We need to explore complete paths from root to leaf nodes
• We must track the cumulative sum along each path
• DFS naturally follows paths to their completion before backtracking
• The recursive nature of DFS makes it easy to maintain the running sum as we traverse down the tree

Conclusion: The flowchart correctly leads us to use a Depth-First Search (DFS) approach for the Path Sum problem. DFS allows us to traverse each root-to-leaf path completely while maintaining the cumulative sum, and backtrack when we reach a leaf to explore other paths. This aligns perfectly with the solution's recursive implementation where we explore both left and right subtrees using dfs(root.left, s) or dfs(root.right, s).

Intuition

When we think about finding a path from root to leaf with a specific sum, we need to explore every possible path in the tree. This naturally suggests a traversal approach.

The key insight is that we can build up the sum incrementally as we traverse down the tree. Starting from the root, we add each node's value to our running sum as we move downward. This way, when we reach a leaf node, we have the complete path sum ready to compare with our target.

Why does DFS work perfectly here? Consider how we explore paths: we want to go all the way down one path to a leaf before exploring another path. This is exactly what DFS does - it goes as deep as possible before backtracking.

The recursive nature of DFS also helps us handle the "backtracking" of our sum naturally. When we pass the cumulative sum s as a parameter to each recursive call, each call gets its own copy of the sum up to that point. When we backtrack from a leaf to explore a sibling path, we automatically "undo" the additions we made going down that branch.

The termination condition becomes clear: we've found a valid path when we're at a leaf node (no children) AND our accumulated sum equals the target. If we're at a leaf but the sum doesn't match, this path doesn't work, so we return false.

The use of or between the left and right recursive calls is crucial - we only need ONE valid path to exist, not all paths. So if either the left subtree OR the right subtree contains a valid path, we return true.

Solution Approach

The solution implements a recursive DFS traversal that tracks the cumulative sum from the root to the current node. Let's walk through the implementation step by step:

1. Main Function Setup: The main function hasPathSum takes the root node and target sum as parameters. It immediately calls a helper function dfs with the root and an initial sum of 0.

2. Recursive DFS Helper Function: The dfs function takes two parameters:

• root: the current node being processed
• s: the cumulative sum from the original root to the current node's parent

3. Base Case - Null Node:

if root is None:
    return False

If we encounter a null node, we return False since there's no path here.

4. Update Running Sum:

s += root.val

We add the current node's value to the cumulative sum. This represents the total sum from the root to the current node.

5. Leaf Node Check:

if root.left is None and root.right is None and s == targetSum:
    return True

When we reach a leaf node (both children are None), we check if our accumulated sum equals the target. If yes, we've found a valid root-to-leaf path.

6. Recursive Exploration:

return dfs(root.left, s) or dfs(root.right, s)

If the current node is not a leaf, we recursively explore both subtrees. The or operator ensures that if either subtree contains a valid path, we return True.

Key Pattern - Path Sum Accumulation: The algorithm maintains the path sum by passing it as a parameter through recursive calls. Each recursive call adds the current node's value to the sum, and when backtracking occurs (returning from a recursive call), we naturally revert to the previous sum state without explicit backtracking code.

Time Complexity: O(n) where n is the number of nodes, as we potentially visit every node once.

Space Complexity: O(h) where h is the height of the tree, representing the maximum recursion depth.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Consider this binary tree with targetSum = 22:

       5
      / \
     4   8
    /   / \
   11  13  4
  / \       \
 7   2       1

Step-by-step execution:

1. Start at root (5):

   • Call dfs(node=5, s=0)
   • Update sum: s = 0 + 5 = 5
   • Not a leaf node, so explore both children

2. Explore left subtree (node 4):

   • Call dfs(node=4, s=5)
   • Update sum: s = 5 + 4 = 9
   • Not a leaf, continue down

3. Go to node 11:

   • Call dfs(node=11, s=9)
   • Update sum: s = 9 + 11 = 20
   • Not a leaf, explore children

4. Check left child (node 7):

   • Call dfs(node=7, s=20)
   • Update sum: s = 20 + 7 = 27
   • This IS a leaf node! Check: 27 == 22? No, return False

5. Backtrack and check right child (node 2):

   • Call dfs(node=2, s=20) (note: s is back to 20)
   • Update sum: s = 20 + 2 = 22
   • This IS a leaf node! Check: 22 == 22? Yes! Return True

6. Propagate the result:

   • Node 11 returns: False or True = True
   • Node 4 returns: True or (not evaluated) = True
   • Root returns: True or (not evaluated) = True

The function returns True because we found the path: 5 → 4 → 11 → 2 with sum = 22.

Key observations from this walkthrough:

• The sum accumulates as we go deeper: 0 → 5 → 9 → 20 → 22
• When we backtrack from node 7 to explore node 2, the sum automatically reverts from 27 back to 20 (the sum at their parent)
• Once we find a valid path (returning True), the or operators short-circuit, avoiding unnecessary exploration
• We only check against targetSum at leaf nodes, not at intermediate nodes

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree. The algorithm performs a depth-first search (DFS) traversal of the tree, visiting each node exactly once. In the worst case, when we need to explore all paths to determine if any path sum equals the target, we must visit every node in the tree.

Space Complexity: O(h), where h is the height of the binary tree. This space is used by the recursive call stack. In the best case (balanced tree), the height is O(log n), resulting in O(log n) space complexity. In the worst case (skewed tree), the height equals n, resulting in O(n) space complexity. The additional space for the parameter s in each recursive call is O(1) per call, which doesn't change the overall space complexity.

Common Pitfalls

1. Incorrectly Checking Non-Leaf Nodes

A frequent mistake is checking if the current sum equals the target at every node, not just at leaf nodes. This leads to incorrect results when internal nodes happen to have the right sum.

Incorrect Implementation:

def dfs(node, current_sum):
    if node is None:
        return False
  
    current_sum += node.val
  
    # WRONG: Checking sum at non-leaf nodes
    if current_sum == targetSum:
        return True
  
    return dfs(node.left, current_sum) or dfs(node.right, current_sum)

Why it's wrong: The problem specifically asks for root-to-leaf paths. If you have a tree like [1, 2] with target sum 1, this incorrect solution would return True even though 1 is not a leaf node.

Correct Approach: Always verify that both children are None before checking the sum:

if node.left is None and node.right is None:
    return current_sum == targetSum

2. Handling Single-Node Trees Incorrectly

Another pitfall is not properly handling the edge case where the tree consists of only a root node (which is also a leaf).

Incorrect Implementation:

def hasPathSum(self, root, targetSum):
    if root is None:
        return False
    if root.val == targetSum:  # WRONG: Not checking if it's a leaf
        return True
    return self.hasPathSum(root.left, targetSum - root.val) or \
           self.hasPathSum(root.right, targetSum - root.val)

Why it's wrong: This would incorrectly return True for a tree [1, 2] with target 1, since it checks the root value without confirming it's a leaf.

Correct Approach: Ensure the leaf check handles single-node trees properly:

if root.left is None and root.right is None:
    return root.val == targetSum

3. Modifying the Target Sum vs. Accumulating Path Sum

While both approaches work, mixing them or implementing them inconsistently can cause errors.

Approach 1 - Subtracting from target (alternative valid approach):

def dfs(node, remaining_sum):
    if node is None:
        return False
    remaining_sum -= node.val
    if node.left is None and node.right is None:
        return remaining_sum == 0
    return dfs(node.left, remaining_sum) or dfs(node.right, remaining_sum)

Approach 2 - Accumulating sum (used in our solution):

def dfs(node, current_sum):
    if node is None:
        return False
    current_sum += node.val
    if node.left is None and node.right is None:
        return current_sum == targetSum
    return dfs(node.left, current_sum) or dfs(node.right, current_sum)

Common Mistake: Mixing the two approaches or forgetting which variable represents what can lead to incorrect comparisons.

4. Empty Tree Edge Case

Not handling the case where the root itself is None.

Incorrect Assumption:

def hasPathSum(self, root, targetSum):
    def dfs(node, current_sum):
        # Assumes root is never None in the initial call
        current_sum += node.val  # This would crash if node is None
        # ...
  
    return dfs(root, 0)

Correct Approach: Always check for None at the beginning of the recursive function, which naturally handles the empty tree case:

def dfs(node, current_sum):
    if node is None:
        return False
    # ... rest of the logic