Log inSign up
easyLeetCodeNot Started

Range Sum of BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given the root 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].

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply BST ordering to eliminate branches outside range queries.
  • Analyze the O(K + H) pruned complexity bound.
  • Implement both recursive and iterative stack pruning.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sum of nodes in range [low, high] on BST.
  • Avoid visiting out-of-range branches.
  • Pruning tree traversal.

Algorithmic Decision Tree:

  • root.val < low: return rangeSumBST(root.right, low, high).
  • root.val > high: return rangeSumBST(root.left, low, high).
  • In range: return root.val + rangeSumBST(root.left) + rangeSumBST(root.right).

Connected Patterns:

Count BST Nodes in a Given RangeTrim a Binary Search TreeSearch in a Binary Search Tree

1. Full Tree Traversal (Unpruned)

Intuition

Perform standard preorder/inorder DFS across all nodes in the tree. For each node, check if its value falls between low and high. If so, add it to the running sum. This visits all N nodes unconditionally in O(N) time.

When to apply: Baseline comparison for generic binary trees where BST ordering is absent.

Algorithm

  1. Traverse every node in the tree using DFS and sum all nodes that satisfy low <= node.val <= high.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int rangeSumBST(TreeNode* root, int low, int high) {
13 if (!root) return 0;
14 int current = (root->val >= low && root->val <= high) ? root->val : 0;
15 return current + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
16 }
17};
18
19int main() {
20 TreeNode* root = new TreeNode(10);
21 root->left = new TreeNode(5);
22 root->right = new TreeNode(15);
23 root->left->left = new TreeNode(3);
24 root->left->right = new TreeNode(7);
25 root->right->right = new TreeNode(18);
26
27 Solution sol;
28 std::cout << "Sum [7, 15]: " << sol.rangeSumBST(root, 7, 15) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

2. Iterative Stack Traversal with BST Pruning

Intuition

Push root to explicit stack. While stack is not empty, pop curr. If curr.val is in range, add to total sum. If curr.val > low, push curr.left (since left subtree might have numbers >= low). If curr.val < high, push curr.right (since right subtree might have numbers <= high). Takes O(K + H) time.

When to apply: When avoiding recursion stack limits.

Algorithm

  1. Use an explicit stack; push only branches that could possibly contain values in [low, high].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 int rangeSumBST(TreeNode* root, int low, int high) {
14 if (!root) return 0;
15 int sum = 0;
16 std::stack<TreeNode*> st;
17 st.push(root);
18
19 while (!st.empty()) {
20 TreeNode* curr = st.top();
21 st.pop();
22
23 if (curr->val >= low && curr->val <= high) {
24 sum += curr->val;
25 }
26 if (curr->left && curr->val > low) {
27 st.push(curr->left);
28 }
29 if (curr->right && curr->val < high) {
30 st.push(curr->right);
31 }
32 }
33 return sum;
34 }
35};
36
37int main() {
38 TreeNode* root = new TreeNode(10);
39 root->left = new TreeNode(5);
40 root->right = new TreeNode(15);
41 root->left->left = new TreeNode(3);
42 root->left->right = new TreeNode(7);
43 root->right->right = new TreeNode(18);
44
45 Solution sol;
46 std::cout << "Sum [7, 15]: " << sol.rangeSumBST(root, 7, 15) << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(K + H) where K is nodes in range and H is tree height
  • Space complexity: O(H) explicit stack space

3. Recursive BST Branch Pruning (Divide and Conquer)

Intuition

1. Base case: if (!root) return 0. 2. If root.val < low: all elements in left subtree are < low. Prune left and return rangeSumBST(root.right, low, high). 3. If root.val > high: all elements in right subtree are > high. Prune right and return rangeSumBST(root.left, low, high). 4. Otherwise low <= root.val <= high: return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high).

When to apply: The standard gold standard solution for technical interviews.

Algorithm

  1. Recursively prune branches based on comparisons with low and high.

BST Range Sum Pruning Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Recurse into left (5) and right (15)
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
root = 10: 7 <= 10 <= 15 -> valid (+10)
Decision / next transition
1
Why this step matters

Recurse into left (5) and right (15).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int rangeSumBST(TreeNode* root, int low, int high) {
13 if (!root) return 0;
14
15 if (root->val < low) {
16 return rangeSumBST(root->right, low, high);
17 }
18 if (root->val > high) {
19 return rangeSumBST(root->left, low, high);
20 }
21
22 return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
23 }
24};
25
26int main() {
27 TreeNode* root = new TreeNode(10);
28 root->left = new TreeNode(5);
29 root->right = new TreeNode(15);
30 root->left->left = new TreeNode(3);
31 root->left->right = new TreeNode(7);
32 root->right->right = new TreeNode(18);
33
34 Solution sol;
35 std::cout << "Sum [7, 15]: " << sol.rangeSumBST(root, 7, 15) << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(K + H) where K is nodes in range and H is tree height
  • Space complexity: O(H) recursion stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Tree Traversal (Unpruned)O(N)O(H) recursion stack spaceTraverse every node in the tree using DFS and sum all nodes that satisfy low <= node.val <= high.O(N)
2.Iterative Stack Traversal with BST PruningO(K + H) where K is nodes in range and H is tree heightO(H) explicit stack spaceUse an explicit stack; push only branches that could possibly contain values in [low, high].O(K + H) where K is nodes in range and H is tree height
3.Recursive BST Branch Pruning (Divide and Conquer)OptimalO(K + H) where K is nodes in range and H is tree heightO(H) recursion stack spaceRecursively prune branches based on comparisons with low and high.O(K + H) where K is nodes in range and H is tree height

Common Pitfalls & Crucial Edge Cases

Reversing inequality check

Recursing left when root.val < low.

Using strict `<` and `>` for range inclusion

Missing boundary values equal to low or high.

Visiting both children unconditionally

Defeating the O(K + H) pruning advantage.

Crucial Edge Cases to Validate:

  • Range completely outside the BST — Prunes down one path and returns 0.
  • Range covers the entire tree — Returns the sum of all nodes in the BST.
  • Single node tree in range — Returns root value.
  • Single node tree out of range — Returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the pruning condition clearly: 'If root.val < low, all nodes in the left subtree are smaller than low, so I prune left.'
  2. Mention that the time complexity is O(K + H) rather than O(N).
  3. Write the concise 6-line recursive solution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When root.val < low, why is it safe to completely ignore the left subtree?

2.What is the worst-case time complexity of the optimal pruning algorithm when [low, high] matches no elements and is smaller than the tree minimum?

3.What is the relation between this problem and 'Count BST Nodes in a Given Range'?

Back to DSA Sheet