Trim a BST

📋

Problem

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.

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

Edge cases: All nodes are within the range → output is the original treeAll nodes are outside the range → output is nullOnly root node is within the range → output is a single node tree

</>

IDE

def trimBST(root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:public TreeNode trimBST(TreeNode root, int low, int high)TreeNode* trimBST(TreeNode* root, int low, int high)function trimBST(root, low, high)

def trimBST(root, low, high):
    # Write your solution here
    pass

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* trimBST(TreeNode* root, int low, int high) {
    // Write your solution here
    return nullptr;
}

function trimBST(root, low, high) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Returns original tree without pruning nodes outside rangeMissing recursive pruning or incorrect subtree replacement when node.val out of range✅ Add recursive calls to trim left and right subtrees and return trimmed subtree based on node.val compared to low and high

Wrong: Prunes nodes equal to low or high valuesUsing strict inequalities (< or >) instead of inclusive (<= or >=) in range checks✅ Change conditions to include equality: if node.val < low return right subtree, if node.val > high return left subtree

Wrong: Fails on empty tree input or single node treesNo base case handling for null root or single node✅ Add base case: if root is None return None; check node.val for single node

Wrong: Only prunes immediate children, missing deeper nodes outside rangeGreedy pruning without recursion on subtrees✅ Use recursive calls to trim entire left and right subtrees fully

Wrong: Algorithm times out on large inputsUsing brute force or rebuilding tree multiple times instead of pruning in O(n)✅ Implement recursive pruning using BST properties to achieve O(n) time complexity

✓

Test Cases

Try testing your code on empty and single node trees to catch base case bugs.

Look for subtle bugs like greedy pruning or boundary condition errors.

Focus on optimizing your pruning to run in linear time using BST properties.

t1_01basic

Input{"root":[3,0,4,null,2,null,null,1],"low":1,"high":3,"n":7}

Expected[3,2,null,1]

⏱ Performance - must finish in 2000ms

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.

💡 Think about recursively pruning subtrees that are out of range.

💡 Use BST properties: if node.val < low, discard left subtree and recurse right; if node.val > high, discard right subtree and recurse left.

💡 Return the node itself if it lies within [low, high], after trimming its children.

Why it failed: Failed to prune nodes outside [1,3]. Possibly missing recursive pruning or incorrect subtree replacement. Fix by correctly returning trimmed left or right subtree when node.val is out of range.

✓ Correctly prunes nodes outside the range and maintains BST structure.

t1_02basic

Input{"root":[5,3,8,2,4,6,10],"low":4,"high":9,"n":7}

Expected[5,4,8,null,null,6]

⏱ Performance - must finish in 2000ms

Nodes 2,3,10 are removed because they are outside [4,9]. The trimmed tree keeps nodes 5,4,8,6.

💡 Check each node's value against the range and prune accordingly.

💡 Remember to recursively trim left and right subtrees after pruning current node.

💡 If node.val < low, return trimmed right subtree; if node.val > high, return trimmed left subtree.

Why it failed: Incorrect pruning of nodes outside [4,9]. Likely not handling subtree returns properly after pruning. Fix by returning trimmed subtrees correctly based on node value.

✓ Successfully trims nodes outside the range and returns a valid BST.

t2_01edge

Input{"root":[],"low":0,"high":10,"n":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree input returns empty tree output.

💡 Consider the base case when root is null.

💡 If root is null, simply return null without further processing.

💡 Ensure your code handles empty input gracefully without errors.

Why it failed: Code crashes or returns non-null for empty input. Fix by adding base case: if root is None, return None immediately.

✓ Correctly handles empty tree input by returning null.

t2_02edge

Input{"root":[5],"low":4,"high":6,"n":1}

Expected[5]

⏱ Performance - must finish in 2000ms

Single node tree with value inside range returns the same single node tree.

💡 Check if single node's value lies within [low, high].

💡 If yes, return the node as is without pruning.

💡 If no, return null.

Why it failed: Fails to return single node when it is within range. Fix by checking node.val against range and returning node if valid.

✓ Correctly returns single node tree when node value is within range.

t2_03edge

Input{"root":[5],"low":6,"high":10,"n":1}

Expected[]

⏱ Performance - must finish in 2000ms

Single node tree with value outside range returns null.

💡 Check if single node's value lies outside [low, high].

💡 If node.val < low or node.val > high, return null.

💡 Ensure pruning works correctly even for single node trees.

Why it failed: Returns node when it should be pruned. Fix by returning null if node.val is outside range.

✓ Correctly prunes single node tree when node value is outside range.

t3_01corner

Input{"root":[10,5,15,3,7,null,18],"low":7,"high":15,"n":7}

Expected[10,7,15]

⏱ Performance - must finish in 2000ms

Nodes 3,5,18 are pruned. Greedy approach that only prunes immediate children fails here.

💡 Beware of pruning only immediate children without recursion.

💡 Use recursive calls to trim entire subtrees properly.

💡 Return trimmed subtrees from recursive calls, not just prune immediate nodes.

Why it failed: Greedy pruning only immediate children misses deeper nodes outside range. Fix by recursively trimming left and right subtrees fully.

✓ Correctly trims entire subtrees recursively, not just immediate children.

t3_02corner

Input{"root":[5,3,7,2,4,6,8],"low":4,"high":7,"n":7}

Expected[5,4,7,null,null,6]

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded pruning: nodes 2 and 8 are pruned correctly, tree remains valid BST.

💡 Remember BST property to decide which subtree to recurse into when pruning.

💡 Do not remove nodes multiple times or assume unbounded duplicates.

💡 Return trimmed subtree correctly to maintain BST structure.

Why it failed: Incorrectly prunes nodes or duplicates due to misunderstanding 0/1 pruning. Fix by pruning each node once and returning trimmed subtree.

✓ Handles pruning correctly respecting BST and 0/1 node presence.

t3_03corner

Input{"root":[8,3,10,1,6,null,14,null,null,4,7,13],"low":5,"high":13,"n":12}

Expected[8,6,10,null,7,null,13]

⏱ Performance - must finish in 2000ms

Off-by-one errors in boundary checks cause incorrect pruning of nodes with values equal to low or high.

💡 Check if your comparisons use <= and >= correctly for boundaries.

💡 Nodes with values equal to low or high should be kept, not pruned.

💡 Adjust conditionals to include equality in range checks.

Why it failed: Prunes nodes equal to low or high due to strict inequalities. Fix by using <= and >= in range checks.

✓ Correctly includes nodes with values equal to low or high.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875],"low":30000,"high":70000,"n":31}

Expected[50000,37500,62500,31250,43750,56250,68750,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null]

⏱ Performance - must finish in 2000ms

n=31 balanced BST, O(n) pruning must complete within 2s.

💡 Use BST properties to prune subtrees without visiting all nodes.

💡 Avoid rebuilding tree from scratch; prune in-place recursively.

💡 Time complexity should be O(n), where n is number of nodes.

Why it failed: Algorithm exceeds time limit due to brute force or repeated traversals. Fix by pruning recursively using BST properties in O(n) time.

✓ Efficient pruning completes within time limit using O(n) recursive approach.

Practice

1. You need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. You are given a binary tree and need to determine if it satisfies the property that for every node, all nodes in its left subtree have smaller values and all nodes in its right subtree have larger values, with no duplicates allowed. Which approach guarantees an optimal solution to this problem?

easy

A. Check each node by comparing it only with its immediate children recursively.

B. Apply a greedy algorithm that validates nodes as soon as they are visited.

C. Use dynamic programming to store subtree min and max values and combine results bottom-up.

D. Perform an inorder traversal and verify that the node values are strictly increasing.

Solution

1. Step 1: Understand BST property

   The BST property requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater, strictly increasing in inorder traversal.

2. Step 2: Recognize inorder traversal pattern

   Inorder traversal of a valid BST produces a strictly increasing sequence of values, so verifying this sequence guarantees correctness efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal yields sorted values for BST [OK]

Hint: Inorder traversal of BST is strictly increasing [OK]

Common Mistakes:

• Only comparing node with immediate children
• Using greedy checks without global ordering
• Confusing subtree min/max with inorder sequence

3. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

4. Suppose the input array can contain duplicate values and you want to build a height-balanced BST that allows duplicates on the right subtree. Which modification to the optimal approach is correct?

hard

A. Change mid calculation to always pick the left middle element to ensure duplicates go to the right subtree.

B. Change the recursive calls to insert duplicates always into the left subtree to maintain balance.

C. Keep mid calculation as is, but when inserting duplicates, always place them in the right subtree during tree construction.

D. Use the brute force approach inserting elements one by one to handle duplicates correctly.

Solution

1. Step 1: Understand duplicate handling

   Duplicates should be consistently placed in the right subtree to maintain BST property.

2. Step 2: Modify insertion logic

   Keep mid calculation unchanged for balance; during node creation, ensure duplicates go to right subtree by design.

3. Step 3: Avoid brute force

   Brute force insertion leads to unbalanced trees and higher complexity.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Maintain balance and BST property by consistent duplicate placement right [OK]

Hint: Keep mid; place duplicates right during construction [OK]

Common Mistakes:

• Changing mid breaks balance
• Inserting duplicates left breaks BST property

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

hard

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

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

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

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

Solution

1. Step 1: Understand the problem extension

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

2. Step 2: Evaluate approaches

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

3. Final Answer:

   Option C -> Option C

4. Quick Check:

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

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

Common Mistakes:

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