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. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

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

3. What is the time complexity of the optimal iterative pruning algorithm for trimming a BST with n nodes, and why?

medium

A. O(log n), because pruning skips entire subtrees quickly.

B. O(n^2), because nested loops may cause repeated visits to nodes.

C. O(n log n), because each pruning step may traverse log n nodes repeatedly.

D. O(n), because each node is visited at most once during pruning.

Solution

1. Step 1: Analyze root adjustment loop

   Root moves down skipping invalid nodes, each step moves to a child, total O(n) in worst case.

2. Step 2: Analyze left and right subtree trimming loops

   Each inner loop removes invalid children by pointer reassignment, each node visited once overall.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node processed once, total O(n) time [OK]

Hint: Each node visited once despite nested loops [OK]

Common Mistakes:

• Assuming pruning is O(log n) due to BST
• Confusing nested loops as O(n^2)

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

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