In the Range Sum of BST problem, you are given the root node of a binary search tree and two integer boundaries: a low limit and a high limit. Your task is to calculate and return the total sum of the values of all nodes that fall inclusively within this [low, high] boundary range. You must efficiently locate and sum up all the nodes whose values are greater than or equal to the low limit, and less than or equal to the high limit.
Example 1
Input: root = [10, 5, 15, 3, 7, null, 18], low = 7, high = 15
Output: 32
Explanation: The tree values falling within the 7 to 15 boundary are 7, 10, and 15. Adding these values together yields 7 + 10 + 15 = 32. Nodes outside this boundary, like 3, 5, and 18, are ignored.
Example 2
Input: root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6], low = 6, high = 10
Output: 23
Explanation: The values between 6 and 10 inclusively are 6, 7, and 10. The sum of these nodes is 6 + 7 + 10 = 23.
Brute Force Approach
A binary search tree has a rigid rule: everything to the left is smaller, and everything to the right is larger. Think of looking for files in a chronologically organized filing cabinet. If you need financial records strictly from the years 2010 to 2015, and you pull open a drawer labeled 2005, you know with absolute certainty that everything further to the left is even older. You do not need to check those folders; you completely skip them and only look right. We can traverse the tree using this exact logic. If a node's value is smaller than our low limit, we completely ignore its left side and only search the right. If it is larger than our high limit, we ignore the right side and only search the left.
Algorithm
Check the base case: if the current node is null, return a sum of 0.
Initialize a running sum variable for the current subtree.
Check if the current node's value falls inside the acceptable boundary (greater than or equal to the low limit, and less than or equal to the high limit). If it does, add its value to the sum.
If the current node's value is strictly greater than the low limit, it means there could still be valid smaller numbers on the left side. Make a recursive call to search the left child and add the result to the sum.
If the current node's value is strictly less than the high limit, there could be valid larger numbers on the right side. Make a recursive call to search the right child and add the result to the sum.
Return the accumulated sum.
Dry Run
Range Sum of BST Brute Dry Run
Solution
// C++ program to implement Range Sum of BST#include <bits/stdc++.h>using namespace std;/* Definition for a binary tree node*/struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: /* Recursively traverses the tree, ignoring entire branches that strictly fall outside the required numerical boundary */ int rangeSumBST(TreeNode* root, int low, int high) { // Base case to stop traversal when reaching a leaf's end if (root == nullptr) { return 0; } int sum = 0; // Accumulate the node's value if it falls within the acceptable boundary if (root->val >= low && root->val <= high) { sum += root->val; } // Search the left branch only if smaller valid numbers might exist there if (root->val > low) { sum += rangeSumBST(root->left, low, high); } // Search the right branch only if larger valid numbers might exist there if (root->val < high) { sum += rangeSumBST(root->right, low, high); } // Return the final calculated sum for this subtree return sum; }};// Driver code starts hereint main() { // Construct the sample tree: [10, 5, 15, 3, 7, null, 18] TreeNode* root = new TreeNode(10); root->left = new TreeNode(5); root->right = new TreeNode(15); root->left->left = new TreeNode(3); root->left->right = new TreeNode(7); root->right->right = new TreeNode(18); // Instantiate the solution object Solution obj; int low = 7; int high = 15; // Retrieve the final calculated sum int result = obj.rangeSumBST(root, low, high); // Output the result to the console cout << result << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes in the tree. In the absolute worst-case scenario, if every single node in the tree falls inside the requested boundary, the algorithm must visit and process every single node.
Space Complexity: O(H), where H is the height of the tree. The recursive call stack will hold at most H active function calls at any given time as it travels down to the deepest leaf.
Optimal Approach
Recursive function calls consume invisible system stack memory. If you are given an extremely deep, unbalanced tree, traversing it recursively could result in a stack overflow error. We can improve our program's structural safety by removing recursion entirely and using an explicit stack to handle our navigation path.
Instead of relying on the computer to automatically remember where to return after checking a node, we manage a physical checklist (a stack data structure). You write down the starting room (the root). You pull it off the list, enter the room, and add its value if it fits your rules. Then, you look at the connected rooms. You write the left room on your checklist only if its numbers could be valid, and you write the right room down only if its numbers could be valid. You repeat this until your checklist is completely empty.
Algorithm
Check if the root is null; if so, return 0.
Initialize a stack to keep track of the nodes we need to visit, and push the root node onto it.
Create a running sum variable starting at 0.
Run a loop that continues as long as the stack is not empty.
Pop the top node from the stack.
Check if the popped node's value is within the
[low, high]boundary. If it is, add it to the sum.If the node's value is strictly greater than the low limit, it means valid smaller numbers could exist, so push the left child onto the stack.
If the node's value is strictly less than the high limit, it means valid larger numbers could exist, so push the right child onto the stack.
Return the finalized sum once the stack empties.
Dry Run
Range Sum of BST Optimal Dry Run
Solution
// C++ program to implement Range Sum of BST#include <bits/stdc++.h>using namespace std;/* Definition for a binary tree node*/struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: /* Iteratively traverses the tree using an explicit stack to avoid system call stack memory limits */ int rangeSumBST(TreeNode* root, int low, int high) { int sum = 0; // Immediately return if the tree is empty if (root == nullptr) { return sum; } // Use a stack to strictly manage which nodes to visit next stack<TreeNode*> st; st.push(root); // Process nodes continuously until the checklist is empty while (!st.empty()) { TreeNode* node = st.top(); st.pop(); // Accumulate the node's value if it falls within the acceptable boundary if (node->val >= low && node->val <= high) { sum += node->val; } // Queue the left child only if smaller valid numbers might exist if (node->val > low && node->left != nullptr) { st.push(node->left); } // Queue the right child only if larger valid numbers might exist if (node->val < high && node->right != nullptr) { st.push(node->right); } } // Return the final calculated sum return sum; }};// Driver code starts hereint main() { // Construct the sample tree: [10, 5, 15, 3, 7, null, 18] TreeNode* root = new TreeNode(10); root->left = new TreeNode(5); root->right = new TreeNode(15); root->left->left = new TreeNode(3); root->left->right = new TreeNode(7); root->right->right = new TreeNode(18); // Instantiate the solution object Solution obj; int low = 7; int high = 15; // Retrieve the final calculated sum int result = obj.rangeSumBST(root, low, high); // Output the result to the console cout << result << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes in the tree. We check nodes and queue them based on the rules, but in the worst case (where every node satisfies the boundary conditions), we visit all N nodes.
Space Complexity: O(H), where H is the height of the tree. The custom stack data structure will store the actively queued nodes, reaching a maximum length equal to the depth of the tree branches being explored.
Interview follow-up Questions
A binary search tree is strictly sorted. Skipping branches is the core optimization that prevents our code from pointlessly checking thousands of nodes. If we know an entire branch only contains numbers smaller than our minimum limit, verifying each one individually is a complete waste of execution time.
Be the first to add a comment.