Path Sum

Difficulty: Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Link: https://leetcode.com/problems/path-sum/

Problem Description

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:


Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:


Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:


Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given a binary tree data structure where each node contains an integer value, determine existence of at least one complete path from root node to any leaf node (terminal node with null children) where the arithmetic sum of all node values along the path equals the specified integer parameter targetSum. Return boolean true if such path exists, otherwise false.

Beginner-Friendly Explanation
Imagine you’re walking through a family tree starting from the oldest ancestor. Each person has a number associated with them. You can only move from parent to child, and you must stop when you reach someone with no children. If you can find one complete line of descent where adding up all the numbers equals a specific target number, you win!

Mathematical Formulation
Let $T$ be a binary tree with $n$ nodes, where each node $v_i$ has value $val(v_i)$ . Let $P = (v_1, v_2, ..., v_k)$ be a path from root $v_1$ to leaf $v_k$ where $v_{i+1}$ is a child of $v_i$ . The path sum is defined as:

\text{sum}(P) = \sum_{i=1}^{k} val(v_i)

The problem reduces to: $\exists P \in \text{AllRootToLeafPaths}(T)$ such that $\text{sum}(P) = \text{targetSum}$

Constraint Analysis

Node count [0, 5000]: Allows O(n) solutions comfortably, O(n²) might be borderline but acceptable. Empty tree must be handled separately.
Node values [-1000, 1000]: Negative values prevent early termination when running sum exceeds target. Integer overflow not a concern.
targetSum [-1000, 1000]: Small range means we don’t need to worry about arithmetic overflow in path sums.

Edge Cases Revealed by Constraints

Empty tree (0 nodes) → always false regardless of targetSum
Single node tree → node value equals targetSum?
All negative values with positive targetSum → impossible paths
All positive values with negative targetSum → impossible paths
Zero values throughout with targetSum = 0 → depends on path lengths
Root with large negative value making targetSum unreachable early

2. Intuition Scaffolding

Real-World Metaphor
Think of navigating a subway system where each station has a toll fee. You start at the central station and must reach the end of a line (no more connections). Your travel card has exactly targetSum credit. Can you find a route that spends exactly all your credit?

Gaming Analogy
In a dungeon crawler game, each room has gold coins (positive or negative). You start at the entrance and must reach a treasure room (dead end). You need exactly targetSum gold to unlock the final chest. Some paths might give too much/little gold.

Math Analogy
This is equivalent to checking if a specific element exists in the set of all possible root-to-leaf sums, where the set is generated through a tree-structured computation graph.

Common Pitfalls

Early false returns: Checking only first leaf found instead of all leaves
Misidentifying leaves: Nodes with one null child aren’t leaves
Null root handling: Forgetting empty tree case
Sum accumulation errors: Passing sum by reference instead of value in recursion
Short-circuit misunderstanding: Thinking we can stop when sum > target (invalid with negatives)

3. Approach Encyclopedia

Brute Force - Path Enumeration

def hasPathSum(root, targetSum):
    if not root: return False
    
    def dfs(node, current_sum):
        if not node: return False
        
        current_sum += node.val
        
        # Check if leaf node
        if not node.left and not node.right:
            return current_sum == targetSum
            
        # Continue searching in both subtrees
        return dfs(node.left, current_sum) or dfs(node.right, current_sum)
    
    return dfs(root, 0)

Complexity Proof

Time: $O(n)$ where $n$ is number of nodes. Each node visited exactly once.
Space: $O(h)$ where $h$ is tree height. Worst-case $O(n)$ for skewed tree, best-case $O(\log n)$ for balanced tree.

Visualization

      5 (sum=5)
     / \
    4(9) 8(13)
   /     / \
  11(20)13(26)4(17)
  /          \
 7(27)        1(18)

Iterative DFS Approach

def hasPathSum(root, targetSum):
    if not root: return False
    
    stack = [(root, 0)]
    while stack:
        node, current_sum = stack.pop()
        current_sum += node.val
        
        if not node.left and not node.right:
            if current_sum == targetSum:
                return True
                
        if node.right:
            stack.append((node.right, current_sum))
        if node.left:
            stack.append((node.left, current_sum))
            
    return False

BFS (Level Order) Approach

from collections import deque

def hasPathSum(root, targetSum):
    if not root: return False
    
    queue = deque([(root, 0)])
    while queue:
        node, current_sum = queue.popleft()
        current_sum += node.val
        
        if not node.left and not node.right:
            if current_sum == targetSum:
                return True
                
        if node.left:
            queue.append((node.left, current_sum))
        if node.right:
            queue.append((node.right, current_sum))
            
    return False

4. Code Deep Dive

Optimal Recursive Solution

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # Edge case: empty tree (Example 3)
        if not root:
            return False
            
        def dfs(node, current_sum):
            # Add current node's value to running total
            current_sum += node.val
            
            # Leaf node check (critical: both children must be None)
            if not node.left and not node.right:
                return current_sum == targetSum
                
            # Explore left subtree if exists
            left_result = False
            if node.left:
                left_result = dfs(node.left, current_sum)
                
            # Short-circuit: return true if left subtree found valid path
            if left_result:
                return True
                
            # Explore right subtree if exists
            if node.right:
                return dfs(node.right, current_sum)
                
            return False
            
        return dfs(root, 0)

Line-by-Line Analysis

Line 3-4: Handle empty tree case (Example 3: root = [], targetSum = 0)
Line 7: current_sum is passed by value, creating independent copies for each path
Line 10: Correct leaf identification (both children null)
Line 11: Final comparison at leaf node
Line 14-16: Depth-first left subtree exploration
Line 18-19: Early termination if left subtree succeeds
Line 22-23: Right subtree exploration with result propagation

Edge Case Handling

Example 1: Path 5→4→11→2 sums to 22, returns True at leaf node 2
Example 2: All paths (1→2=3, 1→3=4) fail to reach targetSum 5
Single node: root = [5], targetSum = 5 → direct comparison at root
Negative values: root = [-2,null,-3], targetSum = -5 → valid path -2→-3

5. Complexity War Room

Hardware-Aware Analysis
For maximum 5000 nodes:

Recursive stack: ~5000 frames × 100 bytes ≈ 500KB (fits in L2 cache)
Iterative approaches: Similar memory footprint
Time complexity O(n) means ~5000 operations → microseconds on modern CPUs

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force DFS	O(n)	O(h)	10/10	✅ Preferred
Iterative DFS	O(n)	O(h)	8/10	✅ Good alternative
BFS Level Order	O(n)	O(w)	7/10	⚠️ Less intuitive
Path Collection	O(n)	O(n²)	5/10	❌ Memory inefficient

w = maximum tree width, h = tree height

6. Pro Mode Extras

Variants Section

Path Sum II (LC 113): Return all paths that sum to target

def pathSum(root, targetSum):
    result = []
    def dfs(node, current_path, current_sum):
        if not node: return
        current_path.append(node.val)
        current_sum += node.val
        if not node.left and not node.right and current_sum == targetSum:
            result.append(current_path.copy())
        dfs(node.left, current_path, current_sum)
        dfs(node.right, current_path, current_sum)
        current_path.pop()
    dfs(root, [], 0)
    return result

Binary Tree Maximum Path Sum (LC 124): Find maximum path sum (any direction)
Path Sum III (LC 437): Count paths summing to target (not necessarily root-to-leaf)

Interview Cheat Sheet

First Mention: “This is a tree traversal problem with O(n) time, O(h) space complexity”
Clarify: “Should I handle negative values? Yes, per constraints”
Edge Cases: “Empty tree, single node, all negative/positive values”
Optimization: “DFS is optimal since we must check all root-to-leaf paths”
Testing: “Verify with provided examples and single node case”

#112 - Path Sum