Path Sum [Tree]

112.Path Sum

Tree

Binary Tree

Depth-First Search

Recursion

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.

Example:

Input:

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

→

Output:

true

Path 5->4->11->2 sums to 22

Algorithm:

1. Handle null root case
2. Check if current node is leaf and matches remaining sum
3. Recursively check left and right subtrees with reduced sum
4. Return true if either path exists

Complexity:

Time: O(n) | Space: O(h) where h is height of tree

Java Solution:

public boolean hasPathSum(TreeNode root, int targetSum) {
    // Base case: empty tree
    if (root == null) return false;
    
    // Check if leaf node matches remaining sum
    if (root.left == null && root.right == null) 
        return targetSum == root.val;
    
    // Recursively check both subtrees
    boolean leftSum = hasPathSum(root.left, targetSum - root.val);
    boolean rightSum = hasPathSum(root.right, targetSum - root.val);
    
    return leftSum || rightSum;
}

Python Solution:

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    # Base case: empty tree
    if not root:
        return False
    
    # Check if leaf node matches remaining sum
    if not root.left and not root.right:
        return targetSum == root.val
    
    # Recursively check both subtrees
    return (self.hasPathSum(root.left, targetSum - root.val) or
            self.hasPathSum(root.right, targetSum - root.val))

C++ Solution:

bool hasPathSum(TreeNode* root, int targetSum) {
    // Base case: empty tree
    if (!root) return false;
    
    // Check if leaf node matches remaining sum
    if (!root->left && !root->right)
        return targetSum == root->val;
    
    // Recursively check both subtrees
    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}