Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Path Sum

LeetCode #112Easy

Root-to-leaf sum == target · carry the remainder down

Given the root of a binary tree and a target sum, return true if there is a root-to-leaf path whose node values add up exactly to the target, and false otherwise.

Asked atAmazonMetaMicrosoft

Recursive DFS (carry remaining down)

time O(n)space O(h)

step 1 / 16

binary tree

call stack ↓

(returned)

Recursive DFS (carry remaining down)


▸
1hasPathSum(node, remaining):
2    remaining -= node.val
3    if leaf: return remaining == 0     // base case
4    if hasPathSum(node.left, remaining): return true
5    if hasPathSum(node.right, remaining): return true
6    return false                       // combine
7// answer = hasPathSum(root, target)

state

target22
start remaining22

line 1Goal: is there a root-to-leaf path whose values sum to 22? The trick is to carry a remainder DOWN instead of summing UP. We start with remaining = 22 and subtract each node's value as we descend. At a leaf, success means remaining hit exactly 0.