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.