Range Sum of BST solution and explanation
Google
9 more videos on this problem
Range Sum of BST - Leetcode 938 - PythonNeetCodeIO · 6:20 · 20K views
Range Sum of BST | Simple Story Recursion | Google | Leetcode 938codestorywithMIK · 14:30 · 14K views
Range Sum of BST (LeetCode 938) | Full solution with animations and examples | Study AlgorithmsNikhil Lohia · 14:00 · 8K views
Range Sum of BST - LeetCode 938 - Python #binarytree #binarysearchtree #leetcodeDeepti Talesra · 12:58 · 962 views
Range Sum of BST - LeetCode Problem #938algoviz-xyz · 6:07 · 757 views
Range Sum of BST - LeetCode 938 - JavaScriptAlgoJS · 5:59 · 555 views
Range Sum of BST | Leetcode 938 | Live coding session 🔥🔥🔥🔥 | O(n)Coding Decoded · 5:18 · 552 views
LeetCode 938 | Range Sum of Binary Search Tree | Solution Explained (Java + Whiteboard)Xavier Elon · 5:45 · 546 views
Leetcode 938 - Range Sum of BST (JAVA Solution Explained!)LC Bear · 7:19 · 213 views
Leetcode 938 | Range Sum of Binary Search Tree(BST) | Range Sum of BST (Detailed solution)The Tech Granth · 6:56 · 184 views
The problem
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 <= 1051 <= low <= high <= 105- All
Node.valare 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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
if not root:
return 0
if root.val < low:
return self.rangeSumBST(root.right, low, high)
if root.val > high:
return self.rangeSumBST(root.left, low, high)
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low)
return rangeSumBST(root.right, low, high);
if (root.val > high)
return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
}
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (!root) return 0;
if (root->val < low)
return rangeSumBST(root->right, low, high);
if (root->val > high)
return rangeSumBST(root->left, low, high);
return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
}
};
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var rangeSumBST = function(root, low, high) {
if (!root) return 0;
if (root.val < low)
return rangeSumBST(root.right, low, high);
if (root.val > high)
return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
};
#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
int rangeSumBST(struct TreeNode* root, int low, int high) {
if (!root) return 0;
if (root->val < low)
return rangeSumBST(root->right, low, high);
if (root->val > high)
return rangeSumBST(root->left, low, high);
return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) { val = value; }
}
public class Solution {
public int RangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low)
return RangeSumBST(root.right, low, high);
if (root.val > high)
return RangeSumBST(root.left, low, high);
return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high);
}
}The Python solution involves recursive function calls, leveraging Python's concise syntax to implement the in-order traversal logic with minimal code.
Time Complexity: O(N), where N is the number of nodes.
Space Complexity: O(H), where H is the height of the tree.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
stack = []
current = root
sum_val = 0
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if low <= current.val <= high:
sum_val += current.val
if current.val > high:
break
current = current.right
return sum_val
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
int sum = 0;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (current.val >= low && current.val <= high) {
sum += current.val;
}
if (current.val > high) break;
current = current.right;
}
return sum;
}
}
#include <stack>
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
std::stack<TreeNode*> stack;
TreeNode* current = root;
int sum = 0;
while (current || !stack.empty()) {
while (current != NULL) {
stack.push(current);
current = current->left;
}
current = stack.top();
stack.pop();
if (current->val >= low && current->val <= high) {
sum += current->val;
}
if (current->val > high) break;
current = current->right;
}
return sum;
}
};
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var rangeSumBST = function(root, low, high) {
let sum = 0;
let stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (current.val >= low && current.val <= high) {
sum += current.val;
}
if (current.val > high) {
break;
}
current = current.right;
}
return sum;
};
#include <stdlib.h>
#include <stdbool.h>
#define MAX_STACK_SIZE 10000
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
void push(struct TreeNode** stack, int* top, struct TreeNode* node) {
if (*top < MAX_STACK_SIZE - 1) {
stack[++(*top)] = node;
}
}
struct TreeNode* pop(struct TreeNode** stack, int* top) {
if (*top >= 0) {
return stack[(*top)--];
}
return NULL;
}
int rangeSumBST(struct TreeNode* root, int low, int high) {
struct TreeNode* stack[MAX_STACK_SIZE];
int top = -1;
int sum = 0;
struct TreeNode* current = root;
while (current || top != -1) {
while (current) {
push(stack, &top, current);
current = current->left;
}
current = pop(stack, &top);
if (current->val >= low && current->val <= high) {
sum += current->val;
}
if (current->val > high) {
break;
}
current = current->right;
}
return sum;
}
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) { val = value; }
}
public class Solution {
public int RangeSumBST(TreeNode root, int low, int high) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
int sum = 0;
while (current != null || stack.Count > 0) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
if (current.val >= low && current.val <= high) {
sum += current.val;
}
if (current.val > high) break;
current = current.right;
}
return sum;
}
}This Python implementation makes use of a manual stack to iterate in an in-order fashion without recursion, accumulating node sums that fall within the specified range.
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 explicit stack.
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
rootis null, return0. - If the value
xofrootis within the range[low, high], then the initial answer of the functiondfs(root)isx, otherwise it is0. - If
x > low, it means that there may be nodes in the left subtree ofrootwith values within the range[low, high], so we need to recursively calldfs(root.left)and add the result to the answer. - If
x < high, it means that there may be nodes in the right subtree ofrootwith values within the range[low, high], so we need to recursively calldfs(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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
const dfs = (root: TreeNode | null): number => {
if (!root) {
return 0;
}
const { val, left, right } = root;
let ans = low <= val && val <= high ? val : 0;
if (val > low) {
ans += dfs(left);
}
if (val < high) {
ans += dfs(right);
}
return ans;
};
return dfs(root);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) (ans int) {
if root == nil {
return 0
}
x := root.Val
if low <= x && x <= high {
ans += x
}
if x > low {
ans += dfs(root.Left)
}
if x < high {
ans += dfs(root.Right)
}
return
}
return dfs(root)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive In-Order Traversal | Time Complexity: O(N), where N is the number of nodes. |
| Iterative In-Order Traversal Using Stack | Time Complexity: O(N), where N is the number of nodes. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive In-Order Traversal | O(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. |
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.