Problem Statement

Path Sum

You are given a binary tree and a target number called targetSum. A binary tree is a set of connected nodes where each node holds a value and can point to up to two children, a left one and a right one. The top node is called the root. A leaf is a node with no children, so it sits at the bottom of a branch. Your job is to answer one yes or no question: is there a path that starts at the root, walks straight down to some leaf, and whose values add up to exactly targetSum? Return true if such a path exists, and false if it does not.

easyTreeTreesTime: O(n) · Space: O(h)

Signals to notice

root-to-leaf pathcheck if sum equals targetrecursive tree traversal

Brute force first

Enumerate all root-to-leaf paths, check sums — same complexity but less elegant. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

DFS: subtract node value from target, check if leaf with remaining = 0. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `root=[1,2,3], targetSum=5`

Call(node=1, target=5): not null; target = 5-1 = 4; node 1 has children -> recurse
Call(node=2, target=4): not null; target = 4-2 = 2; node 2 is a leaf -> return (2==0) = false
Back at node 1: left=false, try right
Call(node=3, target=4): not null; target = 4-3 = 1; node 3 is a leaf -> return (1==0) = false
Back at node 1: left=false OR right=false = false
Return false

What must stay true

At each node, reduce the target by the node's value — a leaf with remaining target 0 means success. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

function hasPathSum(node, target):
    if node is null: return false
    target -= node.val
    if node is a leaf: return target == 0
    return hasPathSum(node.left, target) OR hasPathSum(node.right, target)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Checking non-leaf nodes — the path must go all the way to a leaf (no children). The fix is usually to return to the meaning of each move, not just the steps themselves.

Trees Pattern