Leetcode - 112. Path Sum

🧠 Approach: Recursive DFS

To determine if a path from root to leaf equals a target sum, we use depth-first traversal. At each node, we subtract the node’s value from the target sum and recurse down. If we reach a leaf node and the remaining sum equals the node’s value, we return true.

🔁 Steps:

1. If the node is null, return false.
2. If it's a leaf node, return true if targetSum === node.val.
3. Recurse on the left and right children with the updated sum.
4. Return true if either recursive call returns true.

✅ Code

var hasPathSum = function(root, targetSum) {
    if (root === null) return false;

    // Check for leaf node and target match
    if (root.left === null && root.right === null) {
        return targetSum === root.val;
    }

    // Recurse down to children
    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
};

⏱️ Time Complexity

• O(N) where N is the number of nodes in the tree.
• In the worst case, we may visit every node once.

📦 Space Complexity

• O(H) where H is the height of the tree.
  • Best case (balanced tree): O(log N)
  • Worst case (skewed tree): O(N)
• This is due to the recursive call stack.