Faangprep Logo
LoginRegister
Depth-First Search
Easy

Path Sum

Determine if the tree has a root-to-leaf path summing to a target.
10 min read
Solve on LeetCode
Examples
Input:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output:true
Explain:

The path 5 -> 4 -> 11 -> 2 sums to 22.

Input:root = [1,2,3], targetSum = 5
Output:false
Explain:

Paths are 1->2 (3) and 1->3 (4). No path sums to 5.

Problem Understanding

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Algorithm Strategy (Top-Down State)

We use Pre-order DFS (Top-Down) logic.

Instead of calculating the sum from scratch at every leaf, we subtract the current node's value from the targetSum as we go down.

  1. Consume Value: remaining = target - node.val.
  2. Check Leaf: If node is a leaf (no left, no right) AND remaining == 0, we found a path! Return true.
  3. Recurse: Check dfs(node.left, remaining) OR dfs(node.right, remaining). If either returns true, propagate it up.
  4. Base Case: If node is null, return false.
Interactive Visualization
Step 1 / 7
5
Need 17
4
8
11
13
4
7
2
1
5
0
4
1
8
2
11
3
4
13
5
4
6
7
7
2
8
9
10
11
1
12

Node 5. Target was 22. Subtracting 5. New Target needed: 17.

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep