Abstract / Summary

Find all root to leaf paths in a binary tree where the sum of the node values equals a given target.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (1+ million submissions).

Typical patterns to solve this problem:

• Backtracking
• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution that solves the classic “path sum” problem on a binary tree. The goal is to return every root-to-leaf path whose node values add up to a given target sum. The solution separates the traversal logic into a helper method deeper and a public entry point pathSum. The helper carries the cumulative sum while descending the tree, builds qualifying paths, and aggregates results from both sub-trees.

Key Steps

The algorithm proceeds through a depth-first search that tracks the running total of node values. The first critical operation is the base case that stops recursion when a null node is encountered.

if not root:
    return None

When a node is present, its value is added to the running total.

sumSoFar += root.val

The next decisive step checks whether the current node is a leaf. If it is, the method compares the accumulated sum with the target. A match yields a single-element path wrapped in a list; otherwise the call returns None.

if not root.left and not root.right:
    if sumSoFar == target:
        return [ [ root.val ] ]
    else:
        return None

If the node is not a leaf, the method recursively explores the left child, collects any returned paths, and prefixes each with the current node’s value.

paths = self.deeper(root.left, sumSoFar, target)
if paths:
    for p in paths:
        result.append([ root.val ] + p)

The same pattern is repeated for the right child, ensuring that paths from both sides are merged into a single result list.

paths = self.deeper(root.right, sumSoFar, target)
if paths:
    for p in paths:
        result.append([ root.val ] + p)

Finally, the helper returns the assembled list of qualifying paths.

return result

The public method pathSum guards against an empty tree and initiates the recursion with a zeroed cumulative sum.

if not root:
    return []
return self.deeper(root, 0, targetSum)

Edge Cases Handled

The code explicitly handles the situation where the input tree is empty. By returning an empty list early, it avoids unnecessary recursion and conforms to the expected output format for a tree with no nodes.

When a leaf node is reached, the algorithm distinguishes between a successful match (cumulative sum equals the target) and a mismatch. In the mismatch case, it returns None, which later prevents the leaf’s value from being added to any result path. This distinction ensures that only complete root-to-leaf paths that satisfy the sum condition are reported.

The recursion also gracefully deals with sub-trees that contain no qualifying paths. The if paths: guard filters out None returns, so an empty branch does not contribute spurious entries to the final list.

Performance Optimizations

The implementation leverages in-place accumulation of the sum (sumSoFar += root.val) rather than constructing a new sum object for each recursive call. This reduces the overhead of creating additional integer objects during traversal.

Path construction uses list concatenation ([ root.val ] + p) only when a qualifying sub-path p is already known. By postponing concatenation until a valid path is identified, the algorithm avoids unnecessary list copying for branches that do not lead to a solution.

The helper returns None for dead ends instead of an empty list. This choice allows the caller to perform a simple truthy check (if paths:) rather than iterating over an empty collection, thereby saving iteration cost on branches that yield no results.

Collecting results in a local result list and returning it once per call minimizes the number of intermediate list objects. Each recursive level aggregates its own contributions before passing the combined list upward, which keeps the memory footprint proportional to the number of successful paths rather than the total number of nodes visited.

Imagine a tree made of numbers where you start at the very top. The goal is to walk down all the different branches to reach the bottom. As you step on each number, you carry a little basket and put that number inside it, keeping a running total of how much the numbers add up to as you go.

When you reach the very end of a branch, you check your basket. If the total of the numbers you collected matches the magic target number, you keep that path as a success. If the total is different, you leave that path behind because it is not the one being looked for.

To do this, the computer acts like a curious explorer. It starts at the top and asks if it should go left or right. It keeps diving deeper into the tree, always counting as it explores. When it finds a path that works, it remembers those numbers. The computer looks at every single branch of the tree one by one until it has checked the entire garden of numbers to see which paths add up to the perfect sum.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java							TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java		Rust			Go
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	aylei						Rust
	begeekmyfriend										C
	BigEggStudy					C#
	black-shadows		Python
	charles-wangkai				Java
	chenyanzhe	C++
	DimitrisJim			JS
	everthis			JS
	fartem								Ruby
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost									Go
	JoshCrozier			JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff							Scala
	qiyuangong		Python
	ruoru						Rust
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	varunu28				Java
	vthwang				Java
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality