Path Sum

 Path Sum

You are given the root of a binary tree and an integer targetSum. Your task is to determine whether the tree has any 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

This is because the path 5 → 4 → 11 → 2 adds up to 22.

Best Data Structure for the Job

Binary trees are already built using the classic TreeNode class.

We just need:

A recursive function to traverse the tree, tracking the remaining target sum.

Different Approaches

Approach 1: Recursive (Depth-First Search)

We use recursion to walk through every path from root to leaf. At each node, we subtract the node’s value from the remaining targetSum, and pass it down the recursive call.

When we reach a leaf, we check if the remaining sum equals the leaf’s value.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        // If it's a leaf node, check if the path sum matches
        if (root.left == null && root.right == null)
            return root.val == targetSum;

        // Recursively check left and right subtrees
        return hasPathSum(root.left, targetSum - root.val) ||
               hasPathSum(root.right, targetSum - root.val);
    }
}

 Approach 2: Iterative (Using Stack)

We can simulate DFS using a stack. Each entry in the stack keeps track of the current node and the remaining sum required.

import java.util.Stack;

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();

        nodeStack.push(root);
        sumStack.push(targetSum - root.val);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currSum = sumStack.pop();

            // Check if it's a leaf and the remaining sum is 0
            if (node.left == null && node.right == null && currSum == 0)
                return true;

            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(currSum - node.right.val);
            }
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(currSum - node.left.val);
            }
        }

        return false;
    }
}

⚠️ Common Pitfalls

• Checking only values and not confirming that it’s a root-to-leaf path.

• Forgetting to subtract root.val from targetSum in recursive/iterative calls.

• Not handling null root (empty tree) properly.

📊 Complexity Summary

Approach	Time Complexity	Space Complexity
Recursive DFS	O(n)	O(h) (h = height of tree)
Iterative (Stack)	O(n)	O(h)




• n is the number of nodes in the tree

• h is the height of the tree

🌍 Real-World Use Cases

• Evaluating whether a decision path leads to a specific cost in decision trees

• Checking possible routes in logistics and supply chain optimization

• Verifying security rule enforcement from root to endpoint in system policies

I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)