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

2. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

3. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

4. What is the worst-case time complexity of the optimized recursive BST node deletion algorithm that uses the in-order successor to replace a node with two children?

medium

A. O(h) where h is the height of the BST

B. O(h^2) due to recursive calls and successor search

C. O(log n) always, since BST is balanced

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

Solution

1. Step 1: Identify height-based operations

   Deletion involves searching down the tree (O(h)) and finding the in-order successor, which is also O(h) in worst case.

2. Step 2: Combine operations and recursion

   Successor search and recursive deletion happen along a path of length h, so total time is O(h), not O(h^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time proportional to tree height, not total nodes or squared height [OK]

Hint: Deletion time depends on tree height, not total nodes [OK]

Common Mistakes:

• Assuming balanced BST always (log n)
• Confusing recursion depth with squared complexity
• Thinking successor search adds extra factor

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