How do you approach Range Sum of BST?

A plain traversal summing everything in range is correct but visits every node - the BST property lets you prune.

What is the time complexity of Range Sum of BST?

Time complexity: O(h + k) on a balanced tree; O(n) worst case on a degenerate one.. Space complexity: O(h).

What are common mistakes on Range Sum of BST?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Range Sum of BST

EasyData Structures

Description

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

Use the BST ordering to skip subtrees that cannot contain a qualifying value - do not visit every node.

The tree is given as a level-order array with explicit nulls, where the children of index i sit at 2i + 1 and 2i + 2. An empty array is an empty tree.

Example 1

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15

Output: 32

Example 2

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10

Output: 23

Example 3

Input: root = [1], low = 1, high = 1

Output: 1

Constraints

- 1 <= number of nodes <= 2 * 10^4 - 1 <= Node.val <= 10^5 - 1 <= low <= high <= 10^5 - The input is a valid BST.

Range Sum of BST: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

A plain traversal summing everything in range is correct but visits every node - the BST property lets you prune.
If a node's value is below `low`, everything in its LEFT subtree is smaller still, so skip that whole side.
Symmetrically, if the value exceeds `high`, skip the right subtree. Only recurse into a side that could still contain a match.

The optimal approach

Show the approach: Pruning is the point of the problem

Summing every node and filtering by range gives the right answer in O(n) and misses what is being tested. The BST invariant - everything left is smaller, everything right is larger - means whole subtrees can be ruled out without looking at them.

At each node there are three cases. If the value is less than `low`, every value in the left subtree is smaller still and cannot qualify, so recurse right only. If it exceeds `high`, recurse left only. Otherwise the value counts, and both sides may contain more.

On a balanced tree with a narrow range this turns O(n) into something closer to O(log n + k) for k results, since the traversal descends to the range and covers only the nodes inside it plus the boundary path.

The same pruning idea drives BST search, `floor`/`ceiling` queries, and validating a BST with min/max bounds. Recognizing when an invariant lets you *not* look at data is the transferable skill here.

Time: O(h + k) on a balanced tree; O(n) worst case on a degenerate one.
Space: O(h)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.