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. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

2. Given the following code for deleting a node in a BST, what is the value of root.val after calling deleteNode(root, 3) on the BST constructed by inserting nodes in order: 5, 3, 6?

easy

A. 6

B. 5

C. 3

D. null (root deleted)

Solution

1. Step 1: Construct BST and locate node 3

   BST: root=5, left=3, right=6. Node with value 3 is a leaf (no children).

2. Step 2: Delete node 3

   Since node 3 has no children, deletion returns null for root.left. Root remains 5 with left child null and right child 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Root value unchanged at 5 after deleting leaf 3 [OK]

Hint: Deleting leaf node returns null for that subtree [OK]

Common Mistakes:

• Confusing root with deleted node
• Replacing root value incorrectly
• Assuming root is deleted

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

4. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

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:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Solution

1. Step 1: Identify thread restoration step

   In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.

2. Step 2: Locate missing restoration

   The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing thread removal corrupts tree structure [OK]

Hint: Always restore threads to avoid tree corruption [OK]

Common Mistakes:

• Forgetting to remove threads
• Misplacing next_val assignment
• Incorrect current pointer updates

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