Range Sum of BST

📋

Problem

Imagine you have a large database of user scores stored in a BST, and you want to quickly find the total score of users whose scores fall within a certain range.

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].

The number of nodes in the tree is in the range [1, 10^5].1 ≤ Node.val ≤ 10^61 ≤ low ≤ high ≤ 10^6

Edge cases: Single node tree with value inside range → sum equals node valueSingle node tree with value outside range → sum equals 0All nodes values less than low → sum equals 0

</>

IDE

def rangeSumBST(root: TreeNode, low: int, high: int) -> int:public int rangeSumBST(TreeNode root, int low, int high)int rangeSumBST(TreeNode* root, int low, int high)function rangeSumBST(root, low, high)

def rangeSumBST(root, low, high):
    # Write your solution here
    pass

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int rangeSumBST(TreeNode* root, int low, int high) {
    // Write your solution here
    return 0;
}

function rangeSumBST(root, low, high) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing traversal or incorrect base case.✅ Implement DFS traversal and accumulate node.val if in range; return 0 only if node is null.

Wrong: Sum missing boundary nodesUsing strict inequalities (node.val > low and node.val < high) instead of inclusive (<=, >=).✅ Change condition to 'if low <= node.val <= high' to include boundary nodes.

Wrong: Partial sum missing nodesGreedy approach stopping traversal after first valid node found.✅ Traverse entire tree with pruning, do not stop early after first match.

Wrong: TLE or timeoutNaive traversal without pruning on large inputs.✅ Implement BST pruning: skip left subtree if node.val < low, skip right if node.val > high.

✓

Test Cases

Try testing your solution on single node trees and boundary values to catch base case bugs.

Consider tricky cases like exact boundaries and greedy traps to refine your logic.

Focus on pruning subtrees to improve performance on large inputs.

t1_01basic

Input{"root":[10,5,15,3,7,null,18],"low":7,"high":15}

Expected32

⏱ Performance - must finish in 2000ms

Nodes with values 7, 10, and 15 are within the range. Their sum is 7 + 10 + 15 = 32.

💡 Consider traversing the BST and accumulating values within the range.

💡 Use DFS and check if node values lie between low and high inclusive.

💡 Add node.val to sum only if low <= node.val <= high.

Why it failed: Failed basic case: likely missing inclusive range check or incorrect traversal. Fix by adding 'if low <= node.val <= high' condition before adding node.val.

✓ Correctly sums nodes within the inclusive range using proper traversal.

t1_02basic

Input{"root":[10,5,15,3,7,13,18,1,null,6],"low":6,"high":10}

Expected23

⏱ Performance - must finish in 2000ms

Nodes with values 6, 7, and 10 are within the range. Sum = 6 + 7 + 10 = 23.

💡 Traverse all nodes and accumulate values within [low, high].

💡 Prune branches where node.val < low or node.val > high to optimize.

💡 Ensure to include nodes equal to low or high in the sum.

Why it failed: Incorrect sum due to excluding boundary values or missing nodes in range. Fix by including nodes where node.val == low or node.val == high.

✓ Correctly includes all nodes within the inclusive range and sums them.

t2_01edge

Input{"root":[5],"low":4,"high":6}

Expected5

⏱ Performance - must finish in 2000ms

Single node tree with value 5 inside range [4,6], sum equals 5.

💡 Test with smallest tree possible: single node.

💡 Check if single node value is correctly included if in range.

💡 Return node.val if low <= node.val <= high, else 0.

Why it failed: Fails single node in-range case by returning 0 or ignoring node. Fix by checking node.val against range before summing.

✓ Handles single node trees correctly when node is in range.

t2_02edge

Input{"root":[5],"low":6,"high":10}

Expected0

⏱ Performance - must finish in 2000ms

Single node tree with value 5 outside range [6,10], sum equals 0.

💡 Test single node outside range returns 0.

💡 Ensure no addition if node.val < low or node.val > high.

💡 Return 0 if node.val not in [low, high].

Why it failed: Incorrectly sums node outside range. Fix by adding condition to exclude nodes not in range.

✓ Correctly returns 0 when single node is out of range.

t2_03edge

Input{"root":[2,1,null],"low":3,"high":5}

Expected0

⏱ Performance - must finish in 2000ms

All nodes less than low=3, sum equals 0.

💡 Test tree where all nodes are less than low boundary.

💡 Prune left subtree if node.val < low to avoid unnecessary sums.

💡 Return 0 if no nodes fall within [low, high].

Why it failed: Fails to exclude nodes less than low, summing them incorrectly. Fix by pruning nodes with val < low.

✓ Correctly excludes all nodes less than low and returns 0.

t3_01corner

Input{"root":[10,5,15,3,7,null,18],"low":7,"high":15}

Expected32

⏱ Performance - must finish in 2000ms

Greedy approach fails if it stops at first valid node; correct sum is 32 including 7,10,15.

💡 Beware of greedy stopping after first valid node found.

💡 Use full DFS with pruning, not greedy first-match.

💡 Traverse all relevant nodes, summing all in range, not just first.

Why it failed: Greedy approach sums only first valid node, missing others. Fix by traversing entire tree with pruning, not stopping early.

✓ Correctly sums all nodes in range, avoiding greedy trap.

t3_02corner

Input{"root":[10,5,15,3,7,null,18],"low":15,"high":15}

Expected15

⏱ Performance - must finish in 2000ms

Range with low == high tests exact boundary inclusion; sum is 15.

💡 Test exact boundary condition where low == high.

💡 Ensure nodes equal to low and high are included.

💡 Check condition uses <= and >=, not just < or >.

Why it failed: Fails to include nodes equal to low or high due to strict inequality. Fix by using inclusive range checks (<= and >=).

✓ Correctly includes nodes equal to low and high boundaries.

t3_03corner

Input{"root":[10,5,15,3,7,null,18],"low":1,"high":1000000}

Expected58

⏱ Performance - must finish in 2000ms

Full range includes all nodes: 3+5+7+10+15+18=58.

💡 Test full range to ensure all nodes are summed.

💡 Avoid pruning when range covers entire tree.

💡 Sum all node values correctly without skipping.

Why it failed: Incorrect pruning excludes nodes even when full range is given. Fix by disabling pruning when low and high cover all node values.

✓ Correctly sums all nodes when full range is specified.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218],"low":30000,"high":70000}

Expectednull

⏱ Performance - must finish in 2000ms

Large BST with n=100 nodes, testing O(n) DFS with pruning completes within 2 seconds.

💡 Use DFS with pruning to avoid unnecessary traversals.

💡 Prune left subtree if node.val < low and right if node.val > high.

💡 Avoid full traversal when possible to meet time constraints.

Why it failed: TLE due to naive traversal without pruning. Fix by implementing BST pruning to skip subtrees outside [low, high].

✓ Efficient pruning ensures O(n) or better runtime within time limit.

Practice

1. Consider the following code for finding the lowest common ancestor in a BST. Given the BST below and nodes p=2 and q=8, what value does the function return? BST structure: 6 / \ 2 8 / \ \ 0 4 9 / \ 3 5

easy

A. 2

B. 8

C. 4

D. 6

Solution

1. Step 1: Trace first iteration with current=6

   p=2 and q=8; 2 < 6 and 8 > 6, so current is split point; return 6.

2. Step 2: Confirm no further traversal

   Since p and q lie on different sides of 6, 6 is the LCA.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Split point found at root 6 immediately [OK]

Hint: LCA is where paths to p and q diverge [OK]

Common Mistakes:

• Returning smaller node instead of split point
• Confusing left/right subtree traversal
• Off-by-one error in loop conditions

2. You are given a binary search tree and a value range [low, high]. You need to remove all nodes whose values fall outside this range, ensuring the resulting tree remains a valid BST. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Iteratively prune the BST by adjusting pointers using BST properties without rebuilding the tree.

B. Apply dynamic programming to store subtrees and decide which to keep based on range constraints.

C. Use a greedy approach to remove nodes one by one by checking each node's value and deleting if out of range.

D. Perform an inorder traversal to collect all valid nodes, then rebuild the BST from the sorted list.

Solution

1. Step 1: Understand the problem constraints

   The problem requires trimming nodes outside [low, high] while preserving BST properties efficiently.

2. Step 2: Evaluate approaches

   Rebuilding the tree (A) wastes time and space. Greedy removal (C) is inefficient and may break BST structure. DP (B) is unnecessary and overcomplicates. Iterative pruning (D) leverages BST properties to skip subtrees and adjust pointers in O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterative pruning uses BST properties optimally [OK]

Hint: Use BST properties to prune iteratively for optimal trimming [OK]

Common Mistakes:

• Rebuilding tree wastes space and time
• Greedy removal breaks BST structure

3. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while curr:
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

4. Consider the following buggy code for inserting a value into a BST. Which line contains the subtle bug that causes the insertion to fail silently in some cases?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        insertIntoBST(root.left, val)
    else:
        insertIntoBST(root.right, val)
    return root

medium

A. Line 2: if root is None

B. Line 4: if val < root.val

C. Line 7: insertIntoBST(root.right, val)

D. Line 5: insertIntoBST(root.left, val)

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to insertIntoBST on root.left or root.right do not update the parent's child pointer.

2. Step 2: Identify missing assignment

   Lines 5 and 7 call insertIntoBST but do not assign the returned subtree back to root.left or root.right, so insertion is lost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing assignment causes silent insertion failure [OK]

Hint: Recursive insert must assign returned subtree to parent's child [OK]

Common Mistakes:

• Not updating parent's child pointer
• Confusing base case with recursive step
• Incorrect comparison operator

5. What is the worst-case time complexity of the optimal iterative BST search algorithm when searching for a value in a BST with n nodes and height h?

medium

A. O(log n) always because BSTs are balanced.

B. O(n) because you might have to visit every node in the tree.

C. O(h) because the search path follows the height of the tree.

D. O(1) because the search uses direct indexing.

Solution

1. Step 1: Understand BST height and search path

   The search path length is at most the height h of the BST, as each step moves down one level.

2. Step 2: Analyze worst-case time complexity

   In worst case (unbalanced tree), h can be up to n, but complexity is expressed as O(h), not O(n) directly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search complexity depends on tree height, not total nodes necessarily [OK]

Hint: Time depends on tree height, not total nodes always [OK]

Common Mistakes:

• Assuming O(log n) always, ignoring unbalanced trees