Abstract / Summary

Given the root of a binary search tree and a range, compute the sum of values of all nodes within that range.

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

Typical patterns to solve this problem:

• Binary Search Tree
• 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 rangeSumBST that computes the sum of all node values within a given inclusive range [low, high] in a binary search tree (BST). The core logic is encapsulated in a nested helper function deeper, which performs a depth-first traversal of the tree, accumulating values that satisfy the range condition.

Core Traversal Logic

def deeper(node):
    if not node:
        return 0

    children = deeper(node.left) + deeper(node.right)
    if node.val >= low and node.val <= high:
        return children + node.val
    else:
        return children

The helper receives a single node. The first conditional checks for a null reference, which terminates the recursion and contributes zero to the sum. The next line recursively explores both left and right sub-trees, storing the combined result in children. After the recursive calls return, the current node’s value is examined against the bounds low and high. If the value lies inside the interval, it is added to children; otherwise, only the accumulated sum from the descendants is returned.

Entry Point

return deeper(root)

The public method simply invokes deeper with the root of the BST, initiating the recursive descent.

Edge Cases Handled

When the tree is empty (root is None), the initial call to deeper immediately hits the null check and returns 0, correctly representing an empty sum.

If all node values fall outside the specified range, the condition node.val >= low and node.val <= high never evaluates to true, and the function propagates the sum of zero from each leaf upward, ultimately yielding 0.

When the range boundaries coincide (low == high), the algorithm still correctly includes only nodes whose value exactly matches that single bound, because the inclusive comparison covers equality on both sides.

The recursion naturally accommodates highly unbalanced trees, as each node is visited exactly once regardless of shape, ensuring that even degenerate structures (e.g., a linked-list-like chain) are processed without special handling.

Implicit Performance Optimizations

The implementation leverages a post-order traversal pattern: it first aggregates results from the left and right sub-trees before deciding whether to incorporate the current node’s value. This ordering allows the function to reuse the already computed sums (children) without additional data structures, keeping the memory footprint limited to the call stack.

Because the algorithm does not store intermediate results in auxiliary containers (such as lists or queues), it avoids the overhead of dynamic memory allocation during traversal. The use of a single integer accumulator (children) per call minimizes temporary objects and contributes to faster execution.

The recursion terminates early for null children, preventing unnecessary work on absent sub-trees. Although the code does not explicitly prune branches based on BST ordering properties, the straightforward depth-first approach ensures each node is examined exactly once, which is optimal for a full traversal scenario.

Summary of Execution Flow

The method begins at the root, recursively descends to leaf nodes, aggregates sums from sub-trees, checks each node against the range, and bubbles the partial sums upward. The final integer returned by rangeSumBST represents the total of all node values that satisfy the inclusive range condition.

Imagine a big family tree made of numbers where everyone has a special place. Each person in the tree is holding a number. This code is like a curious little explorer whose job is to find all the numbers that are tucked inside a specific range.

The explorer starts at the very top of the tree, which is called the root. When the explorer reaches someone, they check if that person is even there. If the spot is empty, the explorer just keeps moving. If there is a person, the explorer checks the numbers held by the people to the left and to the right in the tree.

After checking the family members below, the explorer looks at the number held by the person they are currently visiting. If that number is not too small and not too big, it fits perfectly inside the target range. The explorer adds that number to the pile they have been collecting from the children. If the number is outside of the range, the explorer simply moves on without adding it to the pile. This keeps happening until every single branch of the tree has been visited and the total count has been counted.

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++		Java
	leetcode.ca	C++	Python	Java	C#		Go				TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim							C
	everthis					JS
	fartem								Ruby
	fengvyi	C++
	fsq	C++
	halfrost						Go
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune							C
	lkwq007		Python
	muhammadfarhankt						Go
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	vthwang			Java
	yuanliu666									Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
muhammadfarhankt	Go
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python

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