Path Sum

Path Sum

What is this problem about?

The Path Sum problem asks whether a binary tree has a root-to-leaf path where the sum of all node values equals a given target. This easy tree problem uses DFS to subtract the current node value from the target at each step, checking if the target reaches 0 at a leaf. The BFS, DFS, binary tree, and tree interview pattern is the core.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this as a foundational tree traversal problem. It validates recursive DFS on binary trees with a target-tracking parameter. It's often a gateway before Path Sum II and III.

Algorithmic pattern used

Recursive DFS with remaining sum. At each node: subtract node.val from remaining target. If at a leaf (no children) and remaining=0, return true. Recursively check left and right subtrees. Return true if either subtree has a valid path.

Example explanation

Tree: 5→(4→(11→(7,2)),8→(13,4→(5,1))). target=22. Path: 5→4→11→2 = 22. DFS: 22-5=17→17-4=13→13-11=2→leaf 2: 2-2=0 ✓. Return true.

Common mistakes candidates make

• Checking internal nodes as potential "endpoints" (must reach a leaf).
• Not handling null children correctly.
• Off-by-one: subtracting before checking vs checking then subtracting.
• Not returning false when both subtrees fail.

Interview preparation tip

Path Sum I is the simplest tree DFS problem. The pattern: reduce target as you go deeper; return true at a leaf if remaining=0. Three follow-ups exist: Path Sum II (find all paths), Path Sum III (any node to any node), Path Sum IV (encoded as flat array). Start with I and understand the recursive structure before moving to harder variants.