← DSA Atlas
Dedicated problem page · #938

Range Sum of BST

EasyTrees and Binary Search TreesBST range query with pruningRecursive DFS guided by BST ordering
Solve on LeetCode ↗
938
EasyTrees and Binary Search TreesRecursive DFS guided by BST orderingBST range query with pruning

Range Sum of BST

Given the root of a binary search tree and two integers low and high, return the sum of the values of all nodes whose value lies in the inclusive range [low, high].

Open official problem prompt ↗
In plain English

Add up only the BST values that fall within a given inclusive interval.

Picture it like this

Scanning a sorted card catalog for entries between two call numbers: once a card is below your low bound, you know everything to its left is even lower and skip that whole drawer.

Example
Input
root = [10,5,15,3,7,null,18], low = 7, high = 15
Output
32
Why
The in-range nodes are 7, 10, and 15, and 7 + 10 + 15 = 32.
Constraints
The number of nodes is in the range [1, 2*10^4]1 <= Node.val <= 10^51 <= low <= high <= 10^5All Node.val are unique
Pattern lesson

See the pattern, then code

BST range query with pruning
Recognition clue

A sum or search constrained to a value range on a BST is a signal to exploit ordering: whole subtrees can be skipped without inspecting them.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Use the BST property to prune. If a node's value is below low, its entire left subtree is also below low, so only go right; if above high, only go left; otherwise the node counts and both sides may contain in-range values.

New words, made simpleKnow these before the algorithm
BST property
Left descendants are smaller, right descendants are larger than a node.
Pruning
Skipping a subtree entirely because its values cannot fall in range.
Inclusive range
Both low and high themselves count toward the sum.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Full traversal with filter

Correct but ignores the ordering, wasting work on subtrees that cannot qualify.

Visit every node and add it if low <= val <= high.

Time O(n)Space O(h)
Best choicePruned range DFS

Same worst case but skips entire out-of-range subtrees; the idiomatic BST answer.

Use the BST property to descend only into subtrees that can hold in-range values.

Time O(n) worst, faster in practiceSpace O(h)
The rule we keep true

Invariant

Every recursive call returns the exact sum of in-range values within the subtree it is given, and it never descends into a subtree whose values are provably all out of range.

Why this is correct

Reasoning

By the BST property, if node.val < low then all values in its left subtree are also < low and cannot contribute, so recursing right alone is complete; symmetrically for node.val > high. When low <= node.val <= high the node contributes and both subtrees may still hold qualifying values, so both are explored. The recursion covers every node that could be in range, so the total is exact.

The algorithm in three movesSay these aloud before coding
1If the node is null, contribute 0

10 in [7,15] -> add 10, both sides

2If node.val < low, recurse only on the right subtree

5 < 7 -> go right to 7

3If node.val > high, recurse only on the left subtree

15 in range -> add; 18 > 15 pruned

4Otherwise add node.val and recurse on both subtrees

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
100
51
152
33
74
185
1 · Readnode 10
2 · Ask7 <= 10 <= 15?
3 · Update statein range
4 · Resultadd 10, recurse both
Key takeaway

Nodes 7, 10, 15 are summed; the subtrees at 3 and 18 are pruned by the range bounds.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Null base case

    An empty subtree contributes zero to the sum.

  2. 2
    Lines 5-6Prune below low

    If the node is too small, only its right subtree can hold in-range values.

  3. 3
    Lines 7-8Prune above high

    If the node is too large, only its left subtree can qualify.

  4. 4
    Lines 9In-range node

    Count this node and sum both subtrees, which may each contain qualifying values.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • low == high (single value, present or not)
  • Range covering the whole tree (sums everything)
  • Range outside all values (returns 0)
  • Single-node tree
!

Common beginner mistakes

  • Using strict inequalities and dropping nodes equal to low or high
  • Recursing into both subtrees even after determining a node is out of range (losing the pruning benefit)
  • Assuming the input is not a BST and doing an unnecessary full scan
  • Off-by-one on inclusivity of the bounds
Check your understanding

When node.val is below low, why is it safe to ignore the entire left subtree?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split