Abstract / Summary

Count paths in a binary tree where the sum of node values equals a given number.

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 47% (1+ million submissions).

Typical patterns to solve this problem:

• 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 with a method pathSum that counts how many root-to-any-node paths in a binary tree have a sum equal to a given targetSum. The algorithm walks the tree recursively, constructs every path that ends at the current node, checks each path’s total, and accumulates a global counter.

Key Steps

Initializing the Counter

result = 0

A variable result is created in the outer scope of pathSum. It holds the total number of qualifying paths discovered during the traversal. Because the nested function will need to modify this variable, the nonlocal keyword is used later to bind the inner scope to this outer variable.

Defining the Recursive Helper

def deeper(node):
    if not node:
        return []

The helper deeper receives a tree node. The first conditional handles the base case where the node is None. In that situation an empty list is returned, indicating that there are no paths to extend from a missing child.

Building Paths that End at the Current Node

paths = [[node.val]]

When a valid node is present, a new list paths is started containing a single-element path consisting of the node’s own value. This represents the path that begins and ends at the current node.

Extending Paths from the Left Subtree

for p in deeper(node.left):
    paths.append(p + [node.val])

The function recursively obtains all paths that terminate at the left child. Each of those paths is extended by appending the current node’s value, thereby forming a new path that now ends at the current node. The extended path is added to paths.

Extending Paths from the Right Subtree

for p in deeper(node.right):
    paths.append(p + [node.val])

The same extension logic is applied to the right child, ensuring that every path that reaches the current node from either side is captured.

Checking Each Path Against the Target Sum

for p in paths:
    if sum(p) == targetSum:
        nonlocal result
        result += 1

Every constructed path is examined. The built-in sum function computes the total of the node values in the path. If the total matches targetSum, the nonlocal declaration brings result into scope, and the counter is incremented. This step guarantees that all qualifying paths that end at the current node are counted exactly once.

Returning the Collected Paths

return paths

After processing, the list of all paths that end at the current node is returned to the caller. This return value enables the parent invocation to extend those paths further upward the tree.

Initiating the Traversal and Producing the Final Answer

deeper(root)
return result

The recursion starts from the root of the tree. Once the entire structure has been explored, the accumulated result is returned as the answer to the original problem.

Edge Cases Handled

When the input tree is empty (root is None), the initial call to deeper immediately returns an empty list, leaving result at its initial value of zero. Consequently, the method correctly reports that there are no paths matching any target sum.

If the tree consists of a single node, the algorithm creates a one-element path containing that node’s value. The sum check will succeed precisely when the node’s value equals targetSum, yielding a count of one; otherwise the count remains zero.

The implementation does not assume that node values are positive. Negative numbers are incorporated naturally because the sum operation aggregates whatever integer values appear in a path. Therefore, paths that rely on cancellation between positive and negative values are correctly evaluated.

A target sum of zero is also supported. The algorithm will count any path whose cumulative total is zero, including paths that contain a mixture of positive and negative numbers or a solitary node with value zero.

Deeply nested trees are processed without special casing; the recursion proceeds until leaf nodes are reached, and each level builds upon the paths returned from its children.

Performance Optimizations Observed

The code leverages a single depth-first traversal to gather all paths that terminate at each node. By constructing the list of paths in the same recursive call that explores the children, the algorithm avoids the need for separate passes over the tree for each possible starting point. This design reduces the overhead associated with repeatedly locating nodes.

Using the nonlocal keyword to update result eliminates the necessity of propagating a count value through return statements. The counter is modified directly in place, which simplifies the control flow and avoids the creation of additional wrapper objects.

Path construction employs list concatenation (p + [node.val]) rather than inserting at the front of a list. This approach builds each new path by extending an existing list, which is efficient for the typical small-to-moderate length of root-to-node paths in binary trees.

The early return of an empty list for None nodes prevents unnecessary list allocations for missing children, ensuring that only actual nodes contribute to the path collection process. This small guard contributes to lower memory churn during recursion.

Imagine a tree made of numbers instead of leaves. You are a little squirrel starting from the very top of the tree, and your job is to climb all the way down to the bottom by picking different paths through the branches. Every time you step on a number, you put it in your backpack.

The goal is to find how many different ways there are to travel from the top to any bottom point so that the numbers in your backpack add up to exactly the target number you are looking for.

To solve this, the code starts at the top and says hello to the first number. Then it looks at the branches to the left and the right to see where it can go next. It keeps track of every path it takes. Once it reaches the bottom of a path, it pauses to look inside the backpack to see if all those numbers add up to the magic target number. If they do, it adds one point to a tally board. It keeps doing this, exploring every single possible branch, until every path has been checked. Finally, the tally board shows the total count of all the paths that added up to the right amount.

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++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	JS	C#	Rust			Go		TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem							Ruby
	fpdjsns	C++
	fsq			Python
	gouthampradhan		Java
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	MacJim	C++
	qiyuangong		Java
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vli02										C
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666								Kotlin
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Java
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
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