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. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

2. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

3. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

4. Suppose the problem is extended so that multiple pairs of nodes (more than two nodes) are swapped in the BST, possibly non-adjacent. Which of the following modifications to the recovery algorithm is correct and efficient?

hard

A. Use the Morris inorder traversal to detect all violations and store all nodes involved, then sort their values and reassign in inorder traversal.

B. Run the Morris traversal multiple times, each time swapping the first detected violation nodes until no violations remain.

C. Use the brute force approach: inorder traversal to collect all values, sort them, then overwrite the tree nodes in inorder traversal.

D. Modify the Morris traversal to swap nodes immediately upon detecting each violation without storing nodes, fixing all swaps in one pass.

Solution

1. Step 1: Understand the problem extension

   Multiple pairs of nodes swapped means multiple violations, possibly complex to detect and fix in one pass.

2. Step 2: Evaluate approaches

   Morris traversal detects only two nodes swapped optimally; multiple swaps require collecting all values, sorting, and rewriting nodes, which brute force does efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Brute force approach handles multiple swaps correctly by sorting all values [OK]

Hint: Multiple swaps require full value sorting and rewriting [OK]

Common Mistakes:

• Assuming Morris traversal can fix multiple swaps in one pass
• Trying to swap nodes immediately without full detection
• Running multiple passes of Morris traversal inefficiently

5. Suppose the BST validation problem is modified so that duplicate values are allowed only on the right subtree (i.e., node values in the right subtree can be equal to the current node). Which modification to the inorder traversal check correctly validates this variant?

hard

A. Change the comparison to node.val < prev[0] to allow duplicates on the right subtree.

B. Change the comparison to node.val < prev[0] for all nodes except when node is right child, then allow node.val == prev[0].

C. Change the comparison to node.val <= prev[0] to allow duplicates anywhere.

D. Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree.

Solution

1. Step 1: Understand variant allowing duplicates only on right subtree

   Duplicates allowed only if they appear in right subtree, so inorder sequence can have equal values only when moving right.

2. Step 2: Modify comparison accordingly

   During inorder traversal, allow node.val == prev[0] only if current node is right child of previous node; otherwise, enforce strict inequality.

3. Step 3: Reason why other options fail

   Change the comparison to node.val < prev[0] to allow duplicates on the right subtree. allows duplicates anywhere; Change the comparison to node.val <= prev[0] to allow duplicates anywhere. allows duplicates anywhere; Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree. is ambiguous and not implementable in simple inorder traversal without parent info.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Allow duplicates only on right subtree requires conditional equality check [OK]

Hint: Duplicates allowed only on right subtree require conditional comparison [OK]

Common Mistakes:

• Allowing duplicates anywhere
• Ignoring subtree direction in comparison
• Using simple <= everywhere