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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Range Sum of BST • Kevin Naughton Jr. • 30,862 views views
Watch 9 more video solutions →Practice Range Sum of BST with our built-in code editor and test cases.
Practice on FleetCode