How do you check if a root-to-leaf path sums to a target?

Q: How do you check if a root-to-leaf path sums to a target?

**Target Audience:** Beginners preparing for coding interviews; you should know what a binary tree is. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the **Verified** section quotes the real output. ## 1. Why This Even Matters — A Story First You are on a hike with a fixed amount of energy, say 22 snack bars' worth. The trail starts at one trailhead and keeps forking; every trail segment costs a certain number of bars. The trails end at viewpoints with no further forks. Question: is there a route from the trailhead to some viewpoint that uses **exactly** all 22 bars? You do not need to add up every route from scratch. Walk down a fork and keep track of how many bars you still have. At each point, subtract the cost of where you are. When you arrive at a viewpoint

The problem

Question presented to candidate: "Given the root of a binary tree and an integer target, write a Python function that returns True if some path from the root down to a leaf has values adding up to exactly the target. Then tell me how you would return all such paths."

What a strong answer should cover:

Carry the remaining target down: subtract the node's value, and at a leaf check that the remainder is 0.
A leaf has no children; a one-child node is not a leaf, so [1, 2] with target 1 is False.
O(n) time, O(h) space; the short-circuit or stops at the first valid path; negative values mean no pruning.
Follow-up: all paths with backtracking (append, recurse, pop) and a copy at each match.
Python specifics: ints never overflow; store list(path) (a copy) or every stored path is the same list that later gets emptied; the recursion limit of 1000 suggests an iterative (node, remaining) stack for deep trees.

Clarifying questions expected:

"Must the path end at a leaf, and start at the root?"
"Can the values or the target be negative?"

Code / implementation expected: Yes — a short recursive Python function; optionally the iterative stack and the all-paths version.

trees
recursion

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know what a binary tree is. Difficulty: Easy Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the Verified section quotes the real output.

1. Why This Even Matters — A Story First

You are on a hike with a fixed amount of energy, say 22 snack bars' worth. The trail starts at one trailhead and keeps forking; every trail segment costs a certain number of bars. The trails end at viewpoints with no further forks. Question: is there a route from the trailhead to some viewpoint that uses exactly all 22 bars?

You do not need to add up every route from scratch. Walk down a fork and keep track of how many bar

The solution is hidden so you can try first

13 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonRecursive hasPathSum on ten cases, including the one-child trap and negatives

Practice

PythonIterative stack, the null-base-case bug, all matching paths, and 64-bit sums