112. Path Sum

Problem Statement

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.

Examples

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The path 5 → 4 → 11 → 2 sums to 22.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Empty tree has no paths.

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Path definition: What defines a valid path - root to leaf only? (Assumption: Yes - path must be from root to a leaf node, not any internal node)

  2. Leaf node: What is considered a leaf node? (Assumption: A node with no children - both left and right are null)

  3. Empty tree: What should we return for an empty tree? (Assumption: Return false - empty tree has no paths)

  4. Negative values: Can node values and targetSum be negative? (Assumption: Yes - both can be negative per constraints)

  5. Path sum calculation: Should we include the root node in the sum? (Assumption: Yes - sum includes all nodes from root to leaf)

Interview Deduction Process (10 minutes)

Step 1: Brute-Force Approach (2 minutes)

Find all root-to-leaf paths, calculate the sum of each path, and check if any sum equals the target. Use DFS to collect all paths, then check each path’s sum. This approach requires storing all paths, which uses O(n × h) space where h is the height, and O(n) time to traverse and check. This works but uses unnecessary space.

Step 2: Semi-Optimized Approach (3 minutes)

Use DFS with backtracking to build paths incrementally. When reaching a leaf node, check if the current path sum equals the target. This avoids storing all paths but still requires maintaining the current path, which uses O(h) space for the recursion stack and path storage.

Step 3: Optimized Solution (5 minutes)

Use recursive DFS without storing paths. Pass the remaining sum (targetSum - current node value) to child nodes. When reaching a leaf node, check if the remaining sum equals 0 (meaning the path sum equals targetSum). This eliminates the need to store paths entirely, using only O(h) space for the recursion stack. The key insight is that we don’t need to know the actual path values - we only need to track whether a valid path exists, which can be determined by tracking the remaining sum.

Solution Approach

This problem requires checking if there exists a root-to-leaf path with a specific sum. We can use DFS to traverse all paths and check if any path sums to the target.

Key Insights:

  1. Root-to-Leaf Path: Must start at root and end at a leaf node
  2. Backtracking: Subtract current node value from target sum as we traverse
  3. Leaf Check: Only check sum when we reach a leaf node
  4. Early Termination: Return true as soon as we find a valid path

Solution: Recursive DFS with Backtracking

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // From root to leaf, any leaf's value equal (target - path value)
        if(!root) return false;
        if(!root->left && !root->right) {
            return root->val == targetSum;
        }
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

Algorithm Explanation:

  1. Base Case - Empty Node:
    • If root is nullptr, return false (no path exists)
  2. Base Case - Leaf Node:
    • If both children are null, we’ve reached a leaf
    • Check if root->val == targetSum (remaining sum equals node value)
    • Return true if match, false otherwise
  3. Recursive Case:
    • For non-leaf nodes, subtract current node value: targetSum - root->val
    • Recursively check left subtree: hasPathSum(root->left, targetSum - root->val)
    • Recursively check right subtree: hasPathSum(root->right, targetSum - root->val)
    • Return true if either subtree contains a valid path (OR operation)

Why This Works?

The algorithm uses backtracking by:

  • Subtracting the current node’s value from targetSum as we go deeper
  • At each leaf, checking if the remaining targetSum equals the leaf’s value
  • This effectively checks if the path sum equals the original targetSum

Example Walkthrough:

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

Tree structure:
        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1

Path: 5 → 4 → 11 → 2

hasPathSum(5, 22):
  root = 5, has children
  Check left: hasPathSum(4, 22 - 5 = 17)
    root = 4, has children
    Check left: hasPathSum(11, 17 - 4 = 13)
      root = 11, has children
      Check left: hasPathSum(7, 13 - 11 = 2)
        root = 7, leaf node
        Check: 7 == 2? No → return false
      
      Check right: hasPathSum(2, 13 - 11 = 2)
        root = 2, leaf node
        Check: 2 == 2? Yes → return true ✓
      
      return true
    
    return true
  
  return true ✓

Input: root = [1,2,3], targetSum = 5

Tree structure:
    1
   / \
  2   3

hasPathSum(1, 5):
  root = 1, has children
  Check left: hasPathSum(2, 5 - 1 = 4)
    root = 2, leaf node
    Check: 2 == 4? No → return false
  
  Check right: hasPathSum(3, 5 - 1 = 4)
    root = 3, leaf node
    Check: 3 == 4? No → return false
  
  return false || false = false ✓

Complexity Analysis:

  • Time Complexity: O(n)
    • Visit each node at most once
    • n = number of nodes in tree
    • Early termination when path found
  • Space Complexity: O(h)
    • Recursion call stack depth = height of tree
    • Best case (balanced): O(log n)
    • Worst case (skewed): O(n)

Alternative Approaches

Solution 2: Iterative DFS with Stack

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        
        stack<pair<TreeNode*, int>> st;
        st.push({root, targetSum});
        
        while (!st.empty()) {
            auto [node, remaining] = st.top();
            st.pop();
            
            if (!node->left && !node->right && node->val == remaining) {
                return true;
            }
            
            if (node->right) {
                st.push({node->right, remaining - node->val});
            }
            if (node->left) {
                st.push({node->left, remaining - node->val});
            }
        }
        
        return false;
    }
};

Complexity: Same as recursive DFS

Solution 3: Iterative BFS with Queue

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        
        queue<pair<TreeNode*, int>> q;
        q.push({root, targetSum});
        
        while (!q.empty()) {
            auto [node, remaining] = q.front();
            q.pop();
            
            if (!node->left && !node->right && node->val == remaining) {
                return true;
            }
            
            if (node->left) {
                q.push({node->left, remaining - node->val});
            }
            if (node->right) {
                q.push({node->right, remaining - node->val});
            }
        }
        
        return false;
    }
};

Complexity:

  • Time: O(n)
  • Space: O(w) where w is maximum width

Key Insights

  1. Backtracking Pattern: Subtract node value from target as we traverse
  2. Leaf Node Check: Only validate sum at leaf nodes (not internal nodes)
  3. Early Termination: Return true immediately when valid path found
  4. OR Logic: Only need one valid path, not all paths
  5. Path Definition: Must be root-to-leaf (complete path)

Edge Cases

  1. Empty tree: root = null, targetSum = 0 → return false
  2. Single node: root = [1], targetSum = 1 → return true
  3. Single node mismatch: root = [1], targetSum = 2 → return false
  4. Negative values: root = [-2,null,-3], targetSum = -5 → return true
  5. Zero sum: root = [1,-1], targetSum = 0 → return true (if path exists)
  6. No valid path: root = [1,2,3], targetSum = 5 → return false

Common Mistakes

  1. Checking at internal nodes: Validating sum before reaching leaf 
    // WRONG:
if (root->val == targetSum) return true; // ❌ Internal node check
  2. Not handling empty tree: Forgetting null check
  3. Wrong leaf check: Not checking both children are null
  4. Accumulating instead of subtracting: Adding values instead of subtracting from target
  5. Not using OR: Using AND instead of OR for subtree checks
Problem Key Difference
LC 112: Path Sum Check if any root-to-leaf path equals target
LC 113: Path Sum II Return all root-to-leaf paths that equal target
LC 437: Path Sum III Count paths with target sum (any node to any node)
LC 124: Binary Tree Maximum Path Sum Find maximum path sum (can start/end anywhere)

This problem demonstrates backtracking in tree traversal. The key insight is subtracting the current node’s value from the target sum as we traverse, then checking if the remaining sum equals the leaf node’s value at the end of each path.