Path Sum

Check if there exists a root-to-leaf path with given sum.

Language Selection

Choose your preferred programming language

Showing: Python

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 equals 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

Approach 1: Recursive DFS (Optimal)

Algorithm

Use recursion to check if there exists a path from root to leaf with given sum.

Steps:

  1. Base case: if node is null, return false
  2. If node is leaf and sum equals target, return true
  3. Recursively check left and right subtrees with reduced sum
  4. Return true if either subtree has a valid path

Implementation

Python:

def hasPathSum(root, targetSum):
    """
    Check if there exists a root-to-leaf path with given sum
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    if not root:
        return False
    
    # Check if current node is leaf and sum matches
    if not root.left and not root.right:
        return root.val == targetSum
    
    # Recursively check left and right subtrees
    remaining_sum = targetSum - root.val
    return (hasPathSum(root.left, remaining_sum) or 
            hasPathSum(root.right, remaining_sum))

Java:

class Solution {
    /**
     * Check if there exists a root-to-leaf path with given sum
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        // Check if current node is leaf and sum matches
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        
        // Recursively check left and right subtrees
        int remainingSum = targetSum - root.val;
        return hasPathSum(root.left, remainingSum) || 
               hasPathSum(root.right, remainingSum);
    }
}

Go:

func hasPathSum(root *TreeNode, targetSum int) bool {
    /**
     * Check if there exists a root-to-leaf path with given sum
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    if root == nil {
        return false
    }
    
    // Check if current node is leaf and sum matches
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }
    
    // Recursively check left and right subtrees
    remainingSum := targetSum - root.Val
    return hasPathSum(root.Left, remainingSum) || 
           hasPathSum(root.Right, remainingSum)
}

JavaScript:

/**
 * Check if there exists a root-to-leaf path with given sum
 * Time: O(n)
 * Space: O(h) where h is height of tree
 */
function hasPathSum(root, targetSum) {
    if (!root) {
        return false;
    }
    
    // Check if current node is leaf and sum matches
    if (!root.left && !root.right) {
        return root.val === targetSum;
    }
    
    // Recursively check left and right subtrees
    const remainingSum = targetSum - root.val;
    return hasPathSum(root.left, remainingSum) || 
           hasPathSum(root.right, remainingSum);
}

C#:

public class Solution {
    /// <summary>
    /// Check if there exists a root-to-leaf path with given sum
    /// Time: O(n)
    /// Space: O(h) where h is height of tree
    /// </summary>
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        // Check if current node is leaf and sum matches
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        
        // Recursively check left and right subtrees
        int remainingSum = targetSum - root.val;
        return HasPathSum(root.left, remainingSum) || 
               HasPathSum(root.right, remainingSum);
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node exactly once
  • Space Complexity: O(h) - Recursion stack depth equals tree height

Key Insights

  1. Leaf Check: Only check sum when reaching a leaf node
  2. Sum Reduction: Subtract current node value from target sum
  3. Recursive Approach: Most intuitive and elegant solution
  4. Iterative Alternative: Use stack for DFS traversal
  5. Early Termination: Return true as soon as valid path found

Edge Cases

  1. Empty Tree: Should return false
  2. Single Node: Check if node value equals target sum
  3. Negative Values: Handle negative node values correctly
  4. Zero Sum: Handle target sum of zero
  5. Large Trees: Handle trees with many nodes

Test Cases

def test_hasPathSum():
    # Test case 1: Valid path
    root1 = TreeNode(5)
    root1.left = TreeNode(4)
    root1.right = TreeNode(8)
    root1.left.left = TreeNode(11)
    root1.left.left.left = TreeNode(7)
    root1.left.left.right = TreeNode(2)
    root1.right.left = TreeNode(13)
    root1.right.right = TreeNode(4)
    root1.right.right.right = TreeNode(1)
    
    assert hasPathSum(root1, 22) == True
    
    # Test case 2: No valid path
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    
    assert hasPathSum(root2, 5) == False
    
    # Test case 3: Single node
    root3 = TreeNode(1)
    assert hasPathSum(root3, 1) == True
    assert hasPathSum(root3, 2) == False
    
    # Test case 4: Empty tree
    assert hasPathSum(None, 0) == False
    
    print("All tests passed!")

test_hasPathSum()

Follow-up Questions

  1. Path Sum II: Return all root-to-leaf paths with given sum?
  2. Path Sum III: Count number of paths with given sum?
  3. Path Sum IV: Handle path sum in n-ary tree?
  4. Path Sum with Constraints: Add additional constraints?
  5. Path Sum with Weights: Handle weighted edges?

Common Mistakes

  1. Not Checking Leaf: Checking sum at non-leaf nodes
  2. Wrong Sum Calculation: Not reducing sum correctly
  3. Missing Base Cases: Not handling empty tree or single node
  4. Early Return: Not checking both subtrees
  5. Null Checks: Not handling null nodes properly

Interview Tips

  1. Start with Recursion: Most intuitive approach
  2. Explain Leaf Check: Show understanding of root-to-leaf requirement
  3. Handle Edge Cases: Mention empty tree and single node cases
  4. Discuss Trade-offs: Compare recursive vs iterative approaches
  5. Follow-up Ready: Be prepared for Path Sum II and III

Concept Explanations

Path Sum: We need to check if there exists a path from root to any leaf node where the sum of all node values along the path equals the target sum.

Leaf Node: A leaf node is a node with no children. We only check the sum when we reach a leaf node, not at intermediate nodes.

Sum Reduction: As we traverse down the tree, we subtract the current node’s value from the target sum. This way, when we reach a leaf, we only need to check if the remaining sum equals the leaf’s value.

Recursive Approach: We recursively check the left and right subtrees with the reduced sum. If either subtree has a valid path, we return true.

Why Recursion Works: The problem has a recursive structure - if we can find a valid path in a subtree, we can find a valid path in the entire tree.

Iterative Alternative: We can use a stack to simulate the recursive calls, storing both the node and the remaining sum for each recursive call.