DSA problem
Trim a Binary Search Tree
Given the root of a binary search tree and the integers low and high, trim the tree so that all of its elements lie in the inclusive range [low, high]. The relative structure of the remaining elements (i.e., if a node x is an ancestor of y in the trimmed tree, this should still be true in the original) must be preserved. Return the root of the trimmed BST. Multiple valid answers exist when there are ties.
The brute force "rebuild from an in-order list" approach is correct but discards the cheap structural information already present in the BST. A much cleaner solution uses recursion that respects the ordering invariant.
The pivotal observation: if root.val < low, then root and its entire left subtree are all strictly less than low (the left subtree is even smaller than the root), so the whole left half is out of range — we discard the root and recurse only on the right subtree. Symmetrically, if root.val > high, discard root and its right subtree and recurse only on the left. Otherwise the root is in range; trim its two subtrees independently and reattach them as the root's new children.
This procedure visits each node at most once, performing constant work per visit, for O(n) time in the worst case. Space is O(h) for the recursion stack, where h is the height of the tree.
Examples
root = [1,0,2], low = 1, high = 2[1,null,2]root = [3,0,4,null,2,null,null,1], low = 1, high = 3[3,2,null,1]root = [1], low = 1, high = 2[1]Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- 0 <= Node.val <= 10^4
- The value of each node in the tree is unique.
- root is guaranteed to be a valid binary search tree.
- 0 <= low <= high <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.