Pattern visualizer
Path Sum
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. Animated on: Given the root of a binary tree [5,4,8,11,null,13,4,7,2,null,null,null,1] and targetSum = 22, return true if some root-to-leaf path sums to targetSum..
Subtract-as-you-descend DFS with short-circuit OR
time O(n)space O(h)step 1 / 9
7
11
2
4
5
13
8
4
1
Call stack
hasPathSum(5)
line 3
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