Skip to main content
Talentd

Range Sum of BST - Solution & Explanation

EasyTreeDepth-First SearchBinary Search TreeBinary Tree22 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2 * 104].
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • All Node.val are unique.

Approach Overview

Problem Overview: Given the root of a Binary Search Tree and two integers low and high, return the sum of all node values that fall within the inclusive range [low, high]. The BST property helps avoid visiting nodes that cannot contribute to the sum.

Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)

This approach performs a classic in-order traversal (left → node → right) using recursion. Because the tree is a binary search tree, values in the left subtree are smaller and values in the right subtree are larger. While traversing, add the node value to the total if it falls inside [low, high]. You can also prune branches: if node.val < low, skip the left subtree; if node.val > high, skip the right subtree. The traversal visits each relevant node once, giving O(n) time in the worst case and O(h) recursion stack space, where h is the tree height.

This method is simple and expressive. Recursion naturally fits problems involving depth-first search on trees, and the BST ordering allows early pruning that reduces unnecessary work in balanced trees.

Approach 2: Iterative In-Order Traversal Using Stack (O(n) time, O(h) space)

The iterative version simulates recursion with an explicit stack. Start from the root and push nodes while moving left. Pop the top node, process its value, then move to its right subtree. During processing, add the node’s value to the running sum if it lies within [low, high]. Just like the recursive version, the BST ordering can be used to skip subtrees that cannot contain valid values.

The stack holds at most h nodes at a time, giving O(h) space complexity. The algorithm still visits each node at most once, resulting in O(n) time complexity. Choose this approach if you want to avoid recursion depth limits or prefer explicit control of traversal state.

Recommended for interviews: The recursive DFS solution is typically expected because it clearly expresses tree traversal logic and shows you understand the BST ordering optimization. Mentioning subtree pruning based on low and high demonstrates deeper knowledge of tree problems. The iterative stack approach is a solid alternative when recursion is restricted.

Approach 1: Recursive In-Order Traversal

This approach involves performing a recursive in-order traversal to accumulate the sum of nodes within the given value range.

Because of the BST properties, the in-order traversal naturally allows visiting nodes in a sorted order, which means that once the current node value is larger than 'high', you can stop traversing further right subtree. Similarly, if the current node value is smaller than 'low', you can avoid traversing the left subtree further.

The function rangeSumBST recursively explores each node. If the node's value is within the range [low, high], it adds this value to the total sum. If the node's value is less than low, it skips to the node's right subtree. If the node's value is greater than high, it skips to the node's left subtree.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes in the tree since in the worst case we must visit all nodes.
Space Complexity: O(H), where H is the height of the tree (accounting for the recursion stack).

Try this approach in the editor →

Approach 2: Iterative In-Order Traversal Using Stack

This approach uses an iterative method with an explicit stack to facilitate an in-order traversal. Utilizing a stack allows avoiding the function call stack and can handle larger trees without risking stack overflow in languages with limitations on recursion depth.

As we push nodes onto the stack, we continue to the leftmost node, then process nodes and move to the right, ensuring nodes are visited in non-decreasing order. Only nodes within the range are added to the sum.

This C implementation of iterative in-order traversal uses a stack to simulate recursion. We start from the root, push all left children to the stack, and pop them to process, checking if they fall within the range to add to the sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N) where N is the number of nodes.
Space Complexity: O(H) where H is the height of the tree due to the stack usage.

Try this approach in the editor →

Approach 3: DFS

We design a function dfs(root), which represents the sum of the values of all nodes in the subtree with root as the root, and the values are within the range [low, high]. The answer is dfs(root).

The execution logic of the function dfs(root) is as follows:

  • If root is null, return 0.
  • If the value x of root is within the range [low, high], then the initial answer of the function dfs(root) is x, otherwise it is 0.
  • If x > low, it means that there may be nodes in the left subtree of root with values within the range [low, high], so we need to recursively call dfs(root.left) and add the result to the answer.
  • If x < high, it means that there may be nodes in the right subtree of root with values within the range [low, high], so we need to recursively call dfs(root.right) and add the result to the answer.
  • Finally, return the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary search tree.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive In-Order Traversal

Time Complexity: O(N), where N is the number of nodes in the tree since in the worst case we must visit all nodes.
Space Complexity: O(H), where H is the height of the tree (accounting for the recursion stack).

Iterative In-Order Traversal Using Stack

Time Complexity: O(N) where N is the number of nodes.
Space Complexity: O(H) where H is the height of the tree due to the stack usage.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive In-Order TraversalO(n)O(h)Best for clarity and typical interview solutions when recursion is allowed.
Iterative In-Order Traversal (Stack)O(n)O(h)Useful when avoiding recursion or when explicit stack control is preferred.

Video Solution

Range Sum of BST - Leetcode 938 - Python • NeetCodeIO • 20,900 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Sum of BST easy or hard?
Range Sum of BST is classified as an Easy problem on LeetCode with a high acceptance rate. It mainly tests basic tree traversal and understanding of BST properties rather than advanced algorithms.
Range Sum of BST Python/Java solution
A typical Python or Java solution uses recursive DFS. Visit the node, check if its value lies within [low, high], add it to the sum, and recursively explore only the subtrees that could contain valid values. Both languages implement this in O(n) time with O(h) space.
How to solve Range Sum of BST in O(n)?
Traverse the tree using depth-first search and accumulate values that fall inside the range [low, high]. Use the BST property to skip unnecessary branches: ignore the left subtree when node.val < low and ignore the right subtree when node.val > high. This guarantees each relevant node is processed once, giving O(n) time.
What is the best approach for Range Sum of BST?
The most common approach is a depth-first search using recursive in-order traversal. Because the structure is a Binary Search Tree, you can prune branches where values are outside the range [low, high]. This keeps the solution simple while maintaining O(n) worst-case time and O(h) space for the recursion stack.
Is Range Sum of BST asked at Google/Amazon/Meta?
Range Sum of BST is a common easy-level tree question that appears in interview preparation lists for companies like Amazon, Google, and Meta. It tests understanding of binary search trees, DFS traversal, and pruning techniques rather than complex algorithms.
What data structure is used in Range Sum of BST?
The problem is based on a Binary Search Tree (BST). Solutions typically use depth-first search traversal with either recursion or an explicit stack to process nodes in-order while leveraging BST ordering to prune branches.
What is the time complexity of Range Sum of BST?
The worst-case time complexity is O(n), where n is the number of nodes in the tree, because each node may be visited once. With BST pruning, many nodes can be skipped in practice. Space complexity is O(h), where h is the height of the tree due to recursion or the traversal stack.

Ready to solve this problem?

Practice Range Sum of BST with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II