Trim a BST

🎯

Trim a BST

mediumTREEAmazonGoogle

Imagine you have a large database of sorted records represented as a BST, but you only want to keep records within a certain range, discarding all others efficiently.

💡 This problem involves pruning a binary search tree (BST) to keep only nodes within a given range. Beginners often struggle because they try to traverse and rebuild the tree without leveraging BST properties, leading to inefficient or incorrect solutions.

📋

Problem Statement

Given the root of a binary search tree and two integers low and high, trim the tree so that all its elements lie in [low, high]. Trimming the tree means removing nodes whose values are less than low or greater than high. Return the root of the trimmed binary search tree. The resulting tree should still be a valid BST.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^90 <= low <= high <= 10^9

💡

Example

Input"root = [3,0,4,null,2,null,null,1], low = 1, high = 3"

Output[3,2,null,1]

Nodes with values 0 and 4 are removed because they are outside the range [1,3]. The resulting tree keeps nodes 3, 2, and 1.

• All nodes are within the range → output is the original tree
• All nodes are outside the range → output is null
• Only root node is within the range → output is a single node tree
• Range includes only one value → output tree contains nodes with that exact value only

⚠️

Common Mistakes

Not using BST properties and traversing entire tree unnecessarily

Leads to inefficient O(n) traversal even when pruning could skip subtrees

✅ Use BST ordering to skip left or right subtree when node is out of range

Modifying tree nodes incorrectly causing invalid BST

Resulting tree violates BST properties or causes runtime errors

✅ Always assign trimmed left and right subtrees back to node.left and node.right

Forgetting to handle null nodes in recursion base case

Leads to null pointer exceptions or infinite recursion

✅ Add base case to return null when node is null

Rebuilding tree from scratch unnecessarily

Wastes time and space, not leveraging BST pruning

✅ Prune in place using BST properties instead of rebuilding

🧠

Brute Force (Rebuild Tree by Inorder Traversal)

💡 This approach exists to build intuition by explicitly collecting valid nodes and reconstructing the tree, showing the problem can be solved by filtering and rebuilding, but it is inefficient.

Intuition

Traverse the BST inorder to get a sorted list of node values, filter out values outside [low, high], then rebuild a balanced BST from the filtered list.

Algorithm

1. Perform inorder traversal to collect all node values in sorted order.
2. Filter the collected values to keep only those within [low, high].
3. Rebuild a balanced BST from the filtered sorted list.
4. Return the root of the rebuilt BST.

💡 The challenge is realizing that inorder traversal gives sorted nodes, and rebuilding a BST from sorted data is a classic problem, but this approach ignores BST pruning optimizations.

</>

Code

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

def inorder(root, arr):
    if not root:
        return
    inorder(root.left, arr)
    arr.append(root.val)
    inorder(root.right, arr)

def build_bst(nums, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    root = TreeNode(nums[mid])
    root.left = build_bst(nums, start, mid - 1)
    root.right = build_bst(nums, mid + 1, end)
    return root

def trimBST(root, low, high):
    arr = []
    inorder(root, arr)
    filtered = [x for x in arr if low <= x <= high]
    return build_bst(filtered, 0, len(filtered) - 1)

# Driver code to test
if __name__ == '__main__':
    # Construct example tree
    root = TreeNode(3)
    root.left = TreeNode(0)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(1)
    low, high = 1, 3
    trimmed = trimBST(root, low, high)
    # Simple print inorder to verify
    def print_inorder(node):
        if not node:
            return
        print_inorder(node.left)
        print(node.val, end=' ')
        print_inorder(node.right)
    print_inorder(trimmed)

Line Notes

def inorder(root, arr):Defines helper to collect nodes inorder, exploiting BST sorted property

arr.append(root.val)Collects node values in sorted order due to inorder traversal

filtered = [x for x in arr if low <= x <= high]Filters out values outside the allowed range

def build_bst(nums, start, end):Builds balanced BST from sorted list by choosing mid as root

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class TrimBST {
    public static void inorder(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorder(root.left, arr);
        arr.add(root.val);
        inorder(root.right, arr);
    }
    public static TreeNode buildBST(List<Integer> nums, int start, int end) {
        if (start > end) return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums.get(mid));
        root.left = buildBST(nums, start, mid - 1);
        root.right = buildBST(nums, mid + 1, end);
        return root;
    }
    public static TreeNode trimBST(TreeNode root, int low, int high) {
        List<Integer> arr = new ArrayList<>();
        inorder(root, arr);
        List<Integer> filtered = new ArrayList<>();
        for (int x : arr) {
            if (x >= low && x <= high) filtered.add(x);
        }
        return buildBST(filtered, 0, filtered.size() - 1);
    }
    public static void printInorder(TreeNode root) {
        if (root == null) return;
        printInorder(root.left);
        System.out.print(root.val + " ");
        printInorder(root.right);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);
        int low = 1, high = 3;
        TreeNode trimmed = trimBST(root, low, high);
        printInorder(trimmed);
    }
}

Line Notes

public static void inorder(TreeNode root, List<Integer> arr)Collects BST nodes in sorted order via inorder traversal

arr.add(root.val);Adds current node's value to list

List<Integer> filtered = new ArrayList<>();Creates list to hold values within range

return buildBST(filtered, 0, filtered.size() - 1);Rebuilds balanced BST from filtered sorted values

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}
TreeNode* buildBST(const vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;
    int mid = (start + end) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildBST(nums, start, mid - 1);
    root->right = buildBST(nums, mid + 1, end);
    return root;
}
TreeNode* trimBST(TreeNode* root, int low, int high) {
    vector<int> arr;
    inorder(root, arr);
    vector<int> filtered;
    for (int x : arr) {
        if (x >= low && x <= high) filtered.push_back(x);
    }
    return buildBST(filtered, 0, (int)filtered.size() - 1);
}
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(0);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(1);
    int low = 1, high = 3;
    TreeNode* trimmed = trimBST(root, low, high);
    printInorder(trimmed);
    return 0;
}

Line Notes

void inorder(TreeNode* root, vector<int>& arr)Helper to collect BST nodes in sorted order

arr.push_back(root->val);Stores current node's value during inorder traversal

vector<int> filtered;Holds values within the specified range

return buildBST(filtered, 0, (int)filtered.size() - 1);Rebuilds BST from filtered sorted values

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
function inorder(root, arr) {
    if (!root) return;
    inorder(root.left, arr);
    arr.push(root.val);
    inorder(root.right, arr);
}
function buildBST(nums, start, end) {
    if (start > end) return null;
    let mid = Math.floor((start + end) / 2);
    let root = new TreeNode(nums[mid]);
    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);
    return root;
}
function trimBST(root, low, high) {
    let arr = [];
    inorder(root, arr);
    let filtered = arr.filter(x => x >= low && x <= high);
    return buildBST(filtered, 0, filtered.length - 1);
}
// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(0);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(1);
const low = 1, high = 3;
const trimmed = trimBST(root, low, high);
function printInorder(node) {
    if (!node) return;
    printInorder(node.left);
    console.log(node.val);
    printInorder(node.right);
}
printInorder(trimmed);

Line Notes

function inorder(root, arr)Collects nodes in sorted order using inorder traversal

arr.push(root.val);Adds current node's value to array

let filtered = arr.filter(x => x >= low && x <= high);Filters out values outside the range

return buildBST(filtered, 0, filtered.length - 1);Rebuilds BST from filtered sorted values

⏱

Complexity

TimeO(n)

SpaceO(n)

Inorder traversal visits all nodes once (O(n)), filtering is O(n), and rebuilding BST from sorted array is O(n).

💡 For n=20 nodes, this means about 20 visits to collect, 20 checks to filter, and 20 steps to rebuild, totaling roughly 60 operations.

Interview Verdict: Accepted but inefficient for large trees due to extra space and rebuilding

This approach works but wastes time and memory rebuilding the tree instead of pruning in place, so it's good for understanding but not optimal.

🧠

Recursive Pruning Using BST Properties

💡 This approach leverages BST properties to prune nodes in place, avoiding rebuilding and extra space, making it more efficient and elegant.

Intuition

If a node's value is less than low, discard the left subtree and recurse on the right subtree. If greater than high, discard the right subtree and recurse on the left subtree. Otherwise, recursively trim left and right subtrees.

Algorithm

1. If current node is null, return null.
2. If node.val < low, discard left subtree and recurse on right subtree.
3. If node.val > high, discard right subtree and recurse on left subtree.
4. Otherwise, recursively trim left and right subtrees and return current node.

💡 The key insight is pruning entire subtrees without visiting all nodes, which is less obvious initially.

</>

Code

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

def trimBST(root, low, high):
    if not root:
        return None
    if root.val < low:
        return trimBST(root.right, low, high)
    if root.val > high:
        return trimBST(root.left, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(0)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(1)
    low, high = 1, 3
    trimmed = trimBST(root, low, high)
    def print_inorder(node):
        if not node:
            return
        print_inorder(node.left)
        print(node.val, end=' ')
        print_inorder(node.right)
    print_inorder(trimmed)

Line Notes

if not root:Base case: empty subtree returns None

if root.val < low:If node too small, discard left subtree and recurse right

if root.val > high:If node too large, discard right subtree and recurse left

root.left = trimBST(root.left, low, high)Recursively trim left subtree within range

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class TrimBST {
    public static TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) return trimBST(root.right, low, high);
        if (root.val > high) return trimBST(root.left, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
    public static void printInorder(TreeNode root) {
        if (root == null) return;
        printInorder(root.left);
        System.out.print(root.val + " ");
        printInorder(root.right);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);
        int low = 1, high = 3;
        TreeNode trimmed = trimBST(root, low, high);
        printInorder(trimmed);
    }
}

Line Notes

if (root == null) return null;Base case for recursion termination

if (root.val < low) return trimBST(root.right, low, high);Skip left subtree if node too small

if (root.val > high) return trimBST(root.left, low, high);Skip right subtree if node too large

root.left = trimBST(root.left, low, high);Recursively trim left subtree

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) return nullptr;
    if (root->val < low) return trimBST(root->right, low, high);
    if (root->val > high) return trimBST(root->left, low, high);
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(0);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(1);
    int low = 1, high = 3;
    TreeNode* trimmed = trimBST(root, low, high);
    printInorder(trimmed);
    return 0;
}

Line Notes

if (!root) return nullptr;Base case: empty subtree returns null

if (root->val < low) return trimBST(root->right, low, high);Discard left subtree if node too small

if (root->val > high) return trimBST(root->left, low, high);Discard right subtree if node too large

root->left = trimBST(root->left, low, high);Recursively trim left subtree

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
function trimBST(root, low, high) {
    if (!root) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}
// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(0);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(1);
const low = 1, high = 3;
const trimmed = trimBST(root, low, high);
function printInorder(node) {
    if (!node) return;
    printInorder(node.left);
    console.log(node.val);
    printInorder(node.right);
}
printInorder(trimmed);

Line Notes

if (!root) return null;Base case for recursion termination

if (root.val < low) return trimBST(root.right, low, high);Skip left subtree if node too small

if (root.val > high) return trimBST(root.left, low, high);Skip right subtree if node too large

root.left = trimBST(root.left, low, high);Recursively trim left subtree

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited at most once. Space is O(h) due to recursion stack where h is tree height.

💡 For a balanced tree with n=20, height h ~ 5, so max 5 recursive calls on stack at once.

Interview Verdict: Accepted and efficient for large BSTs

This is the preferred approach in interviews because it uses BST properties to prune efficiently without extra space.

🧠

Iterative Pruning Using BST Properties

💡 This approach avoids recursion by iteratively adjusting the root and pruning subtrees, useful when recursion depth is a concern.

Intuition

First move the root to a valid node within [low, high]. Then iteratively trim left and right subtrees by skipping nodes outside the range.

Algorithm

1. Move root down until root.val is within [low, high].
2. Iteratively trim the left subtree: if left child is less than low, move left pointer to its right child.
3. Iteratively trim the right subtree: if right child is greater than high, move right pointer to its left child.
4. Return the adjusted root.

💡 This approach is trickier because it requires careful pointer manipulation without recursion, but it achieves the same pruning.

</>

Code

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

def trimBST(root, low, high):
    # Move root to valid range
    while root and (root.val < low or root.val > high):
        if root.val < low:
            root = root.right
        elif root.val > high:
            root = root.left
    if not root:
        return None
    # Trim left subtree
    cur = root
    while cur:
        while cur.left and cur.left.val < low:
            cur.left = cur.left.right
        cur = cur.left
    # Trim right subtree
    cur = root
    while cur:
        while cur.right and cur.right.val > high:
            cur.right = cur.right.left
        cur = cur.right
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(0)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(1)
    low, high = 1, 3
    trimmed = trimBST(root, low, high)
    def print_inorder(node):
        if not node:
            return
        print_inorder(node.left)
        print(node.val, end=' ')
        print_inorder(node.right)
    print_inorder(trimmed)

Line Notes

while root and (root.val < low or root.val > high):Adjust root until it lies within the range

if root.val < low: root = root.rightIf root too small, move to right subtree

while cur.left and cur.left.val < low: cur.left = cur.left.rightPrune left subtree nodes less than low

while cur.right and cur.right.val > high: cur.right = cur.right.leftPrune right subtree nodes greater than high

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class TrimBST {
    public static TreeNode trimBST(TreeNode root, int low, int high) {
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low) root = root.right;
            else if (root.val > high) root = root.left;
        }
        if (root == null) return null;
        TreeNode cur = root;
        while (cur != null) {
            while (cur.left != null && cur.left.val < low) {
                cur.left = cur.left.right;
            }
            cur = cur.left;
        }
        cur = root;
        while (cur != null) {
            while (cur.right != null && cur.right.val > high) {
                cur.right = cur.right.left;
            }
            cur = cur.right;
        }
        return root;
    }
    public static void printInorder(TreeNode root) {
        if (root == null) return;
        printInorder(root.left);
        System.out.print(root.val + " ");
        printInorder(root.right);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);
        int low = 1, high = 3;
        TreeNode trimmed = trimBST(root, low, high);
        printInorder(trimmed);
    }
}

Line Notes

while (root != null && (root.val < low || root.val > high))Adjust root until it is within the range

if (root.val < low) root = root.right;Move root right if too small

while (cur.left != null && cur.left.val < low) cur.left = cur.left.right;Prune left subtree nodes less than low

while (cur.right != null && cur.right.val > high) cur.right = cur.right.left;Prune right subtree nodes greater than high

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* trimBST(TreeNode* root, int low, int high) {
    while (root && (root->val < low || root->val > high)) {
        if (root->val < low) root = root->right;
        else if (root->val > high) root = root->left;
    }
    if (!root) return nullptr;
    TreeNode* cur = root;
    while (cur) {
        while (cur->left && cur->left->val < low) {
            cur->left = cur->left->right;
        }
        cur = cur->left;
    }
    cur = root;
    while (cur) {
        while (cur->right && cur->right->val > high) {
            cur->right = cur->right->left;
        }
        cur = cur->right;
    }
    return root;
}
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(0);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(1);
    int low = 1, high = 3;
    TreeNode* trimmed = trimBST(root, low, high);
    printInorder(trimmed);
    return 0;
}

Line Notes

while (root && (root->val < low || root->val > high))Adjust root until it lies within the range

if (root->val < low) root = root->right;Move root right if too small

while (cur->left && cur->left->val < low) cur->left = cur->left->right;Prune left subtree nodes less than low

while (cur->right && cur->right->val > high) cur->right = cur->right->left;Prune right subtree nodes greater than high

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
function trimBST(root, low, high) {
    while (root && (root.val < low || root.val > high)) {
        if (root.val < low) root = root.right;
        else if (root.val > high) root = root.left;
    }
    if (!root) return null;
    let cur = root;
    while (cur) {
        while (cur.left && cur.left.val < low) {
            cur.left = cur.left.right;
        }
        cur = cur.left;
    }
    cur = root;
    while (cur) {
        while (cur.right && cur.right.val > high) {
            cur.right = cur.right.left;
        }
        cur = cur.right;
    }
    return root;
}
// Driver code
const root = new TreeNode(3);
root.left = new TreeNode(0);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(1);
const low = 1, high = 3;
const trimmed = trimBST(root, low, high);
function printInorder(node) {
    if (!node) return;
    printInorder(node.left);
    console.log(node.val);
    printInorder(node.right);
}
printInorder(trimmed);

Line Notes

while (root && (root.val < low || root.val > high))Adjust root until it is within the range

if (root.val < low) root = root.right;Move root right if too small

while (cur.left && cur.left.val < low) cur.left = cur.left.right;Prune left subtree nodes less than low

while (cur.right && cur.right.val > high) cur.right = cur.right.left;Prune right subtree nodes greater than high

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited at most once. Space is constant as no recursion stack is used.

💡 For n=20, this means about 20 iterations with no extra memory for recursion.

Interview Verdict: Accepted and useful when recursion depth is a concern

This approach is optimal and avoids recursion stack overflow, but is more complex to implement correctly.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the recursive pruning approach (Approach 2) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Rebuild Tree)	O(n)	O(n)	No	Yes	Mention only - never code
2. Recursive Pruning	O(n)	O(h)	Yes (if unbalanced)	No	Code this approach
3. Iterative Pruning	O(n)	O(1)	No	No	Mention or code if recursion depth is a concern

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach using inorder traversal and rebuilding.Step 3: Explain the recursive pruning leveraging BST properties.Step 4: Optionally mention iterative pruning to avoid recursion.Step 5: Code the recursive pruning approach and test.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of BST properties, recursion, and ability to optimize from brute force to efficient pruning.

Common Follow-ups

• What if the tree is very unbalanced? → Recursive approach still works but may cause stack overflow.
• Can you do this iteratively? → Yes, by adjusting pointers without recursion.

💡 Follow-ups often test your ability to handle edge cases and optimize recursion to iteration.

🔍

Pattern Recognition

When to Use

1) Problem involves BST and pruning nodes; 2) Range or boundary constraints given; 3) Need to maintain BST validity; 4) Asked to remove nodes outside range.

Signature Phrases

trim the BSTall elements lie in [low, high]remove nodes outside range

NOT This Pattern When

General binary tree pruning without BST properties or problems requiring balancing trees

Similar Problems

Delete Node in a BST - also modifies BST structureLowest Common Ancestor of a BST - uses BST ordering to prune search space

Practice

1. You are given a binary search tree (BST) that has become skewed after multiple insertions and deletions, causing inefficient search operations. Which approach best guarantees transforming this BST into a balanced BST with minimal height to optimize search times?

easy

A. Perform a preorder traversal and rebuild the BST using the traversal order.

B. Use a greedy approach to rotate nodes locally to balance the tree without full traversal.

C. Apply dynamic programming to find the optimal subtree splits for balancing.

D. Perform an inorder traversal to collect nodes in sorted order, then rebuild the BST by recursively choosing the middle node as root.

Solution

1. Step 1: Understand traversal order for BST

   Inorder traversal of a BST produces nodes in sorted order, which is essential for rebuilding a balanced BST.

2. Step 2: Rebuild balanced BST from sorted nodes

   Choosing the middle node as root recursively ensures minimal height and balanced structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal + middle node rebuild -> balanced BST [OK]

Hint: Inorder traversal yields sorted nodes for balanced rebuild [OK]

Common Mistakes:

• Using preorder or postorder traversal which do not guarantee sorted order
• Trying local rotations greedily without global structure knowledge
• Misapplying DP where recursion on sorted nodes suffices

2. Consider the following BSTIterator implementation using Morris traversal:

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    pre.right = None
                    self.next_val = self.current.val
                    self.current = self.current.right

Given the BST with nodes 2 (root), 1 (left child), and 3 (right child), what is the value of next_val after the first call to _advance() during initialization?

easy

A. 3

B. 2

C. 1

D. null

Solution

1. Step 1: Trace _advance() starting at root=2

   Since root has a left child (1), find predecessor of 2 in left subtree: node 1 has no right child, so set 1.right = 2 and move current to 1.

2. Step 2: At current=1, no left child, so set next_val=1 and move current to 1.right which points back to 2 (thread).

   Return from _advance() with next_val=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   First inorder element is 1, matches next_val after first advance [OK]

Hint: Morris traversal first yields leftmost node [OK]

Common Mistakes:

• Assuming next_val is root value initially
• Forgetting thread creation
• Confusing next_val with current node

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

4. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early

5. Suppose the BST nodes can have duplicate values and you want to compute the sum of all nodes within [low, high], including duplicates. Which modification to the iterative DFS with pruning approach correctly handles duplicates without losing efficiency?

hard

A. Use a hash set to track visited nodes to avoid double counting duplicates.

B. Remove pruning and traverse all nodes to ensure duplicates are counted.

C. Keep pruning logic unchanged since BST property guarantees duplicates are on one side only.

D. Modify pruning to include equal values on both left and right subtrees when node.val equals low or high.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on either left or right subtree depending on insertion rules, so pruning must consider equality carefully.

2. Step 2: Adjust pruning for duplicates

   When node.val equals low or high, both subtrees may contain duplicates within range, so both should be explored.

3. Step 3: Avoid removing pruning entirely

   Removing pruning loses efficiency; using a hash set is unnecessary as nodes are unique objects.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Pruning adjusted for equality handles duplicates efficiently [OK]

Hint: Include equal values on both sides when pruning [OK]

Common Mistakes:

• Removing pruning loses efficiency
• Assuming duplicates only on one side