Range Sum of BST

🎯

Range Sum of BST

easyTREEAmazonGoogleFacebook

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.

💡 This problem involves traversing a binary search tree (BST) to sum values within a range. Beginners often struggle because they may not leverage the BST property to prune unnecessary branches, leading to inefficient solutions.

📋

Problem Statement

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

💡

Example

Input"root = [10,5,15,3,7,null,18], low = 7, high = 15"

Output32

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

• Single node tree with value inside range → sum equals node value
• Single node tree with value outside range → sum equals 0
• All nodes values less than low → sum equals 0
• All nodes values greater than high → sum equals 0

⚠️

Common Mistakes

Not pruning subtrees based on BST property

Solution visits all nodes, leading to inefficient O(n) time even when pruning is possible

✅ Add conditions to skip left or right subtree when node value is out of range

Including nodes outside the range in sum

Incorrect sum output with extra values added

✅ Check if node.val is within [low, high] before adding to sum

Not handling null nodes in recursion or iteration

Runtime errors or exceptions due to null pointer dereference

✅ Add base case to return 0 or skip null nodes

Using recursion without considering stack overflow for deep trees

Stack overflow error on very deep or skewed trees

✅ Use iterative approach with explicit stack or tail recursion optimization

🧠

Brute Force (Traverse All Nodes)

💡 This approach exists to establish a baseline solution by visiting every node regardless of its value, helping beginners understand the problem and tree traversal basics.

Intuition

Traverse the entire tree and accumulate the sum of node values that fall within the given range.

Algorithm

1. Start at the root node.
2. Traverse the entire tree using DFS (preorder, inorder, or postorder).
3. For each node, check if its value is within [low, high].
4. If yes, add the node's value to the sum.

💡 The challenge is to understand that this approach does not use BST properties and visits every node, which is straightforward but inefficient.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rangeSumBST(root, low, high):
    def dfs(node):
        if not node:
            return 0
        total = 0
        if low <= node.val <= high:
            total += node.val
        total += dfs(node.left)
        total += dfs(node.right)
        return total
    return dfs(root)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(rangeSumBST(root, 7, 15))  # Output: 32

Line Notes

class TreeNode:Defines the TreeNode class to represent nodes in the BST.

def dfs(node):Defines a helper function for recursive traversal.

if not node:Base case to stop recursion at leaf's child.

if low <= node.val <= high:Check if current node's value is within the range to add it.

total += dfs(node.left)Recursively accumulate sum from left subtree.

total += dfs(node.right)Recursively accumulate sum from right subtree.

return dfs(root)Starts the DFS traversal from the root and returns the total sum.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int sum = 0;
        if (root.val >= low && root.val <= high) sum += root.val;
        sum += rangeSumBST(root.left, low, high);
        sum += rangeSumBST(root.right, low, high);
        return sum;
    }

    public static void main(String[] args) {
        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);
        Solution sol = new Solution();
        System.out.println(sol.rangeSumBST(root, 7, 15)); // 32
    }
}

Line Notes

class TreeNode {Defines the TreeNode class representing nodes in the BST.

if (root == null) return 0;Base case to stop recursion when node is null.

if (root.val >= low && root.val <= high) sum += root.val;Add node's value if it lies within the range.

sum += rangeSumBST(root.left, low, high);Recurse on left subtree to accumulate sum.

sum += rangeSumBST(root.right, low, high);Recurse on right subtree to accumulate sum.

return sum;Return the accumulated sum for this subtree.

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        int sum = 0;
        if (root->val >= low && root->val <= high) sum += root->val;
        sum += rangeSumBST(root->left, low, high);
        sum += rangeSumBST(root->right, low, high);
        return sum;
    }
};

int main() {
    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);
    Solution sol;
    cout << sol.rangeSumBST(root, 7, 15) << endl; // 32
    return 0;
}

Line Notes

struct TreeNode {Defines the TreeNode struct representing nodes in the BST.

if (!root) return 0;Stops recursion at null nodes.

if (root->val >= low && root->val <= high) sum += root->val;Add node's value if in range.

sum += rangeSumBST(root->left, low, high);Accumulate sum from left subtree.

sum += rangeSumBST(root->right, low, high);Accumulate sum from right subtree.

return sum;Return the accumulated sum for this subtree.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rangeSumBST(root, low, high) {
    if (!root) return 0;
    let sum = 0;
    if (root.val >= low && root.val <= high) sum += root.val;
    sum += rangeSumBST(root.left, low, high);
    sum += rangeSumBST(root.right, low, high);
    return sum;
}

// Example usage:
const root = new TreeNode(10,
    new TreeNode(5, new TreeNode(3), new TreeNode(7)),
    new TreeNode(15, null, new TreeNode(18))
);
console.log(rangeSumBST(root, 7, 15)); // 32

Line Notes

function TreeNode(val, left = null, right = null) {Defines the TreeNode constructor for BST nodes.

if (!root) return 0;Base case to end recursion at null nodes.

if (root.val >= low && root.val <= high) sum += root.val;Add node's value if it lies within the range.

sum += rangeSumBST(root.left, low, high);Recursively add sum from left subtree.

sum += rangeSumBST(root.right, low, high);Recursively add sum from right subtree.

return sum;Return the accumulated sum for this subtree.

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit every node once, so time is O(n). The recursion stack can go as deep as the tree height h.

💡 For n=1000 nodes, this means roughly 1000 operations and stack depth up to tree height.

Interview Verdict: Accepted but not optimal

This approach works but is inefficient because it doesn't use BST properties to skip subtrees.

🧠

Optimized DFS with BST Pruning

💡 This approach improves efficiency by leveraging BST properties to skip subtrees that cannot contain values in the range.

Intuition

If the current node's value is less than low, then all nodes in its left subtree are also less and can be skipped. Similarly, if the node's value is greater than high, skip the right subtree.

Algorithm

1. Start at the root node.
2. If node is null, return 0.
3. If node's value is less than low, recurse only on right subtree.
4. If node's value is greater than high, recurse only on left subtree.
5. Otherwise, add node's value and recurse on both subtrees.

💡 The key insight is pruning entire subtrees to reduce unnecessary work.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rangeSumBST(root, low, high):
    if not root:
        return 0
    if root.val < low:
        return rangeSumBST(root.right, low, high)
    if root.val > high:
        return rangeSumBST(root.left, low, high)
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(rangeSumBST(root, 7, 15))  # Output: 32

Line Notes

if not root:Base case to stop recursion at null nodes.

if root.val < low:Skip left subtree because all values there are smaller than low.

if root.val > high:Skip right subtree because all values there are greater than high.

return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)Add current node and recurse both sides if within range.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low) return rangeSumBST(root.right, low, high);
        if (root.val > high) return rangeSumBST(root.left, low, high);
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }

    public static void main(String[] args) {
        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);
        Solution sol = new Solution();
        System.out.println(sol.rangeSumBST(root, 7, 15)); // 32
    }
}

Line Notes

if (root == null) return 0;Stop recursion at null nodes.

if (root.val < low) return rangeSumBST(root.right, low, high);Skip left subtree when node value less than low.

if (root.val > high) return rangeSumBST(root.left, low, high);Skip right subtree when node value greater than high.

return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);Add current node and recurse both subtrees if in range.

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        if (root->val < low) return rangeSumBST(root->right, low, high);
        if (root->val > high) return rangeSumBST(root->left, low, high);
        return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
    }
};

int main() {
    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);
    Solution sol;
    cout << sol.rangeSumBST(root, 7, 15) << endl; // 32
    return 0;
}

Line Notes

if (!root) return 0;Stop recursion at null nodes.

if (root->val < low) return rangeSumBST(root->right, low, high);Skip left subtree if node value less than low.

if (root->val > high) return rangeSumBST(root->left, low, high);Skip right subtree if node value greater than high.

return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);Add current node and recurse both subtrees if in range.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rangeSumBST(root, low, high) {
    if (!root) return 0;
    if (root.val < low) return rangeSumBST(root.right, low, high);
    if (root.val > high) return rangeSumBST(root.left, low, high);
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}

// Example usage:
const root = new TreeNode(10,
    new TreeNode(5, new TreeNode(3), new TreeNode(7)),
    new TreeNode(15, null, new TreeNode(18))
);
console.log(rangeSumBST(root, 7, 15)); // 32

Line Notes

if (!root) return 0;Base case to stop recursion at null nodes.

if (root.val < low) return rangeSumBST(root.right, low, high);Skip left subtree if node value less than low.

if (root.val > high) return rangeSumBST(root.left, low, high);Skip right subtree if node value greater than high.

return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);Add current node and recurse both subtrees if in range.

⏱

Complexity

TimeO(n) in worst case, O(log n) average

SpaceO(h)

In worst case (skewed tree), we visit all nodes. Average case prunes subtrees, reducing nodes visited to O(log n).

💡 For balanced trees with 1000 nodes, this approach visits far fewer nodes than brute force.

Interview Verdict: Accepted and efficient

This approach is preferred in interviews because it uses BST properties to optimize traversal.

🧠

Iterative DFS with Stack and BST Pruning

💡 This approach uses an explicit stack to avoid recursion, which can be helpful in languages with limited recursion depth or to demonstrate iterative skills.

Intuition

Use a stack to simulate DFS traversal, applying the same pruning logic as the recursive approach to skip unnecessary subtrees.

Algorithm

1. Initialize a stack with the root node.
2. While the stack is not empty, pop a node.
3. If node is null, continue.
4. If node's value is within [low, high], add it to sum and push both children.
5. If node's value is less than low, push only right child.
6. If node's value is greater than high, push only left child.

💡 The key is managing the stack and applying pruning conditions correctly.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rangeSumBST(root, low, high):
    stack = [root]
    total = 0
    while stack:
        node = stack.pop()
        if node:
            if low <= node.val <= high:
                total += node.val
                stack.append(node.left)
                stack.append(node.right)
            elif node.val < low:
                stack.append(node.right)
            else:  # node.val > high
                stack.append(node.left)
    return total

# Example usage:
if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(rangeSumBST(root, 7, 15))  # Output: 32

Line Notes

stack = [root]Initialize stack with root to start iterative DFS.

while stack:Loop until all nodes to visit are processed.

node = stack.pop()Pop the current node to process.

if low <= node.val <= high:If node in range, add value and push both children.

elif node.val < low:If node less than low, push only right child to prune left subtree.

else:If node greater than high, push only left child to prune right subtree.

return totalReturn the accumulated sum after processing all relevant nodes.

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int total = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (node.val >= low && node.val <= high) {
                    total += node.val;
                    stack.push(node.left);
                    stack.push(node.right);
                } else if (node.val < low) {
                    stack.push(node.right);
                } else {
                    stack.push(node.left);
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {
        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);
        Solution sol = new Solution();
        System.out.println(sol.rangeSumBST(root, 7, 15)); // 32
    }
}

Line Notes

Stack<TreeNode> stack = new Stack<>();Create stack to hold nodes for iterative DFS.

stack.push(root);Start traversal from root node.

while (!stack.isEmpty()) {Process nodes until stack is empty.

if (node.val >= low && node.val <= high) {If node in range, add value and push both children.

else if (node.val < low) {If node less than low, push right child only to prune left subtree.

else {If node greater than high, push left child only to prune right subtree.

return total;Return the accumulated sum after processing all relevant nodes.

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        stack<TreeNode*> stk;
        stk.push(root);
        int total = 0;
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            if (node) {
                if (node->val >= low && node->val <= high) {
                    total += node->val;
                    stk.push(node->left);
                    stk.push(node->right);
                } else if (node->val < low) {
                    stk.push(node->right);
                } else {
                    stk.push(node->left);
                }
            }
        }
        return total;
    }
};

int main() {
    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);
    Solution sol;
    cout << sol.rangeSumBST(root, 7, 15) << endl; // 32
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to hold nodes for iterative traversal.

stk.push(root);Initialize stack with root node.

while (!stk.empty()) {Process nodes until stack is empty.

if (node->val >= low && node->val <= high) {Add node value if in range and push both children.

else if (node->val < low) {Push right child only to prune left subtree.

else {If node value greater than high, push left child only to prune right subtree.

return total;Return the accumulated sum after processing all relevant nodes.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rangeSumBST(root, low, high) {
    const stack = [root];
    let total = 0;
    while (stack.length > 0) {
        const node = stack.pop();
        if (node) {
            if (node.val >= low && node.val <= high) {
                total += node.val;
                stack.push(node.left);
                stack.push(node.right);
            } else if (node.val < low) {
                stack.push(node.right);
            } else {
                stack.push(node.left);
            }
        }
    }
    return total;
}

// Example usage:
const root = new TreeNode(10,
    new TreeNode(5, new TreeNode(3), new TreeNode(7)),
    new TreeNode(15, null, new TreeNode(18))
);
console.log(rangeSumBST(root, 7, 15)); // 32

Line Notes

const stack = [root];Initialize stack with root node for iterative DFS.

while (stack.length > 0) {Continue until all nodes are processed.

if (node.val >= low && node.val <= high) {Add node value if in range and push both children.

else if (node.val < low) {Push right child only to prune left subtree.

else {If node value greater than high, push left child only to prune right subtree.

return total;Return the accumulated sum after processing all relevant nodes.

⏱

Complexity

TimeO(n) worst case, O(log n) average

SpaceO(h)

Stack stores nodes to visit; pruning reduces nodes visited on average.

💡 For balanced trees, this approach visits fewer nodes and uses stack space proportional to tree height.

Interview Verdict: Accepted and iterative alternative

This approach is useful when recursion is limited or iterative solutions are preferred.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimized recursive approach with pruning is the best choice for most interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(h)	Yes	N/A	Mention only - never code
2. Optimized DFS with BST Pruning	O(n) worst, O(log n) average	O(h)	Yes	N/A	Code this approach
3. Iterative DFS with Stack and BST Pruning	O(n) worst, O(log n) average	O(h)	No	N/A	Optional iterative alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach by traversing all nodes.Step 3: Explain how BST properties allow pruning to optimize.Step 4: Implement the optimized recursive solution.Step 5: Optionally, discuss iterative implementation.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Understanding of BST properties, ability to optimize traversal, coding correctness, and handling edge cases.

Common Follow-ups

• What if the tree is not a BST? → Must traverse all nodes, no pruning possible.
• How to handle very large trees? → Use iterative approach or tail recursion optimization.

💡 These follow-ups test your understanding of BST assumptions and scalability considerations.

🔍

Pattern Recognition

When to Use

1) Input is a BST, 2) Query involves range or order, 3) Need to aggregate values, 4) Can prune based on BST ordering

Signature Phrases

sum of values in rangebinary search treeinclusive range [low, high]

NOT This Pattern When

Range sum in arrays or segment trees, which require different data structures and approaches.

Similar Problems

Range Sum Query - Mutable - similar range sum but with updatesKth Smallest Element in a BST - uses BST ordering to find kth element

Practice

1. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

2. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

3. What is the space complexity of the optimal Morris inorder traversal approach used to recover a BST with two swapped nodes, and why might some candidates mistakenly believe it is higher?

medium

A. O(1) because Morris traversal modifies tree pointers temporarily without extra data structures

B. O(n) due to storing node values during traversal

C. O(h) where h is tree height due to recursion stack in inorder traversal

D. O(log n) because of balanced tree height and implicit stack usage

Solution

1. Step 1: Understand Morris traversal space usage

   Morris traversal uses threaded binary tree pointers to traverse without recursion or stack, so no extra space beyond a few pointers.

2. Step 2: Identify common misconception

   Candidates often confuse it with recursive or stack-based inorder traversal, which uses O(h) space, or with storing values in a list, which uses O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal achieves O(1) space by temporarily modifying tree pointers [OK]

Hint: Morris traversal uses threaded pointers, no stack needed [OK]

Common Mistakes:

• Assuming recursion stack space applies
• Confusing storing values with traversal space
• Believing temporary pointer changes increase space

4. Suppose you want to balance a BST but now the tree nodes can have duplicate values and the BST property is relaxed to allow duplicates on either side. Which modification to the balancing algorithm ensures the resulting tree remains valid and balanced?

hard

A. Use preorder traversal instead of inorder to collect nodes, then rebuild.

B. Modify the middle index calculation to always pick the left middle to keep duplicates on left.

C. During inorder traversal, collect nodes preserving duplicates order, then choose middle node as root as usual.

D. Sort the collected nodes by value before rebuilding to handle duplicates properly.

Solution

1. Step 1: Understand duplicates in BST with relaxed property

   Inorder traversal still produces nodes in non-decreasing order preserving duplicates order.

2. Step 2: Rebuild balanced BST using middle node selection

   Choosing middle node as root maintains balance and respects duplicates order.

3. Step 3: Avoid sorting or preorder traversal

   Sorting is unnecessary and preorder breaks sorted order; left middle bias skews balance.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inorder traversal + middle node rebuild works with duplicates [OK]

Hint: Inorder traversal preserves duplicates order for balanced rebuild [OK]

Common Mistakes:

• Using preorder traversal losing sorted order
• Sorting nodes again causing unnecessary overhead
• Biasing middle index causing unbalanced tree

5. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged