Abstract / Summary

Check if there exists a route from the top to the bottom of a binary tree where the numbers along the path add up to a given target sum.

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 55% (4+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth First Search
• 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 Solution class that determines whether a binary tree contains a root-to-leaf path whose node values sum to a specified target. The public method hasPathSum serves as the entry point, delegating the actual traversal to a helper method named deeper. The algorithm explores the tree depth-first, accumulating the running total of node values along each path and checking the sum when a leaf is reached.

Core Logic

The first logical step is the guard clause in hasPathSum that immediately returns False when the input tree is empty. This handles the edge case where no nodes exist, ensuring the function does not attempt further recursion on a None reference.

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    if not root:
        return False
    return self.deeper(root, 0, targetSum)

The helper method deeper receives three parameters: the current node, the cumulative sum accumulated so far, and the target sum. The method begins by checking whether the current node is None. If it is, the recursion terminates for that branch, returning False. This condition protects against attempts to access attributes of a non-existent node and naturally terminates paths that reach beyond leaf nodes.

def deeper(self, root, sumSoFar, target):
    if not root:
        return False

Next, the node’s value is added to the running total. By updating sumSoFar in place, the algorithm avoids the need for auxiliary data structures to track the path, thereby keeping the memory footprint minimal.

    sumSoFar += root.val

The algorithm then determines whether the current node is a leaf by checking the absence of both left and right children. When a leaf is encountered, the accumulated sum is compared directly to the target. If they match, the method returns True; otherwise, it returns False. This leaf-level check is crucial because only root-to-leaf paths are considered valid, and it prevents premature acceptance of partial paths.

    if not root.left and not root.right:
        return sumSoFar == target

If the node is not a leaf, the method proceeds to explore its subtrees. It recursively invokes deeper on the left child and the right child, passing along the updated sum. The use of the logical or operator enables short-circuit evaluation: as soon as a valid path is found in either subtree, the recursion unwinds, and the result propagates upward without unnecessary further calls. This behavior constitutes a performance optimization, reducing the number of recursive invocations in cases where a matching path exists early in the traversal.

    return self.deeper(root.left, sumSoFar, target) or self.deeper(root.right, sumSoFar, target)

Edge Cases Handled

The implementation gracefully manages several edge conditions. An empty tree triggers the early return in hasPathSum, yielding False without invoking the helper. A tree consisting of a single node is correctly processed: the leaf check evaluates the sole node, and the sum comparison determines whether the node’s value equals the target. The algorithm also accommodates negative values because the cumulative sum is updated arithmetically without any assumptions about sign. Deeply nested trees are traversed recursively, and the early termination via short-circuit or ensures that once a qualifying path is discovered, deeper recursion on sibling branches is avoided.

Implicit Optimizations

The design leverages in-place accumulation of the path sum, eliminating the need for constructing explicit path lists or stacks. By passing the running total as an argument, each recursive call works with a simple integer, which is cheap to copy and compare. The short-circuit or in the return statement provides a built-in pruning mechanism: when the left subtree yields a successful path, the right subtree is not explored, saving both time and stack space. Additionally, the early leaf check prevents unnecessary recursion beyond leaf nodes, ensuring that the algorithm terminates as soon as a complete path is evaluated.

Overall, the code presents a concise depth-first search that efficiently determines the existence of a root-to-leaf path matching a target sum, handling empty structures, single-node trees, negative values, and deep hierarchies while employing straightforward optimizations to limit work once a solution is found.

Imagine a tree made of numbers where starting from the top you pick a bumpy path that goes all the way down to a leaf at the very bottom. Each branch has its own special number attached to it. The computer starts by looking at the top of this tree and travels down while keeping a running total of all the numbers it sees along the way. Every time the computer reaches one of the tips at the end of a branch, it checks if that total matches a secret number given at the start. If the path leads to a tip and the total matches, the goal is achieved. If the path does not match or it reaches a dead end without finding the answer, the computer goes back up and tries a different branch to see if that one works instead. It keeps trying every single path until it finds one that sums up to the secret number or runs out of paths to check.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Java			Rust	JS		Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim					C
	everthis							JS
	fartem								Ruby
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost									Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vthwang			Java
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
XiaotaoGuo	C++
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