Path Sum
Subtract-as-you-descend DFS with short-circuit OR
time O(n)space O(h)
Instead of accumulating a running total downward and comparing it to targetSum at each leaf, subtract every node's value from targetSum as you descend. A leaf that brings the remaining balance to exactly 0 marks a valid path — and the left/right OR short-circuits, so once one side finds a match the other subtree is never explored.
Subtract-as-you-descend DFS with short-circuit OR
step 1 / 9
7
11
2
4
5
13
8
4
1
Call stack
hasPathSum(5)
Enter node 5. remaining = 22 - 5 = 17. Not a leaf, so try the left subtree first.
Pseudocode
1FUNCTION hasPathSum(node, remaining):2 IF node = null: RETURN false3 remaining <- remaining - node.val4 IF node.left = null AND node.right = null:5 RETURN remaining = 06 RETURN hasPathSum(node.left, remaining) OR hasPathSum(node.right, remaining)
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Enter node 5. remaining = 22 - 5 = 17. Not a leaf, so try the left subtree first.
- Enter node 4. remaining = 17 - 4 = 13. Not a leaf, so try the left subtree first.
- Enter node 11. remaining = 13 - 11 = 2. Not a leaf, so try the left subtree first.
- Node 7 is a leaf. remaining = 2 - 7 = -5, not 0, so this path doesn't work. Return false and backtrack.
- Node 2 is a leaf. remaining = 2 - 2 = 0, which is exactly 0 — this root-to-leaf path sums to the target. Return true.
- Back at node 11: the left subtree found nothing, so the result is whatever the right subtree returned — true.
- Back at node 4: the left subtree already returned true, so return true immediately — the right subtree is never even visited.
- Back at node 5: the left subtree already returned true, so return true immediately — the right subtree is never even visited.
- hasPathSum returns true: the path 5 → 4 → 11 → 2 sums to 22. Node 8's entire subtree (13 and the second 4) was never visited, because the left branch already succeeded.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.