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:
[1, 2 * 104].1 <= Node.val <= 1051 <= low <= high <= 105Node.val are unique.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.
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.
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).
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.
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.
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:
root is null, return 0.x of root is within the range [low, high], then the initial answer of the function dfs(root) is x, otherwise it is 0.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.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.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.
| Approach | Complexity |
|---|---|
| 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. |
| Iterative In-Order Traversal Using Stack | Time Complexity: O(N) where N is the number of nodes. |
| DFS | — |
| 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. |
Range Sum of BST - Leetcode 938 - Python • NeetCodeIO • 20,504 views views
Watch 9 more video solutions →Practice Range Sum of BST with our built-in code editor and test cases.
Practice on FleetCode