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.

Consume Value: remaining = target - node.val.
Check Leaf: If node is a leaf (no left, no right) AND remaining == 0, we found a path! Return true.
Recurse: Check dfs(node.left, remaining) OR dfs(node.right, remaining). If either returns true, propagate it up.
Base Case: If node is null, return false.

Interactive Visualization

Step 1 / 1

Empty Heap

Initializing...

Custom Input

Visualize subtracting the node value from the target as we traverse down.

Previous Problem

Maximum Depth of Binary Tree

Next Problem

Validate Binary Search Tree

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.