Path Sum

Problem Statement

You’re a pathfinder in a binary tree, seeking a root-to-leaf path where the node values sum to a target. Return true if such a path exists, false otherwise. This easy-level DFS journey is a treasure trail—sum those nodes!

Example

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

Tree:

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

Output: true (5+4+11+2 = 22)

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

Output: false (No path sums to 1)

Input: root = [], targetSum = 0

Output: false

Code

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) || 
               hasPathSum(root.right, targetSum - root.val);
    }
}
            

class Solution:
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or \
               self.hasPathSum(root.right, targetSum - root.val)
            

function hasPathSum(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) return targetSum === root.val;
    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
}
            

Explanation

• DFS Insight: Subtract node value from target, check leaves for exact match.
• Flow: Recurse down, reducing targetSum; at leaf, check if remainder is 0.
• Example Walkthrough: [5,4,11,7,2], 22 → 5→4→11→2 = 22, true.
• Edge Case: Negative sums, empty tree, single node—all handled.
• BFS Alt: Queue with (node, sum) pairs—less common but viable.

Note