Trim a Binary Search Tree
Medium · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
Given the root of a binary search tree and two bounds low and high, remove every node whose value lies outside [low, high].
The trimmed tree must keep the relative structure of the surviving nodes: any node that remains keeps its surviving descendants as descendants. The trimmed tree is unique, and its root may differ from the original root.
Return the root of the trimmed tree (None, shown as [], when nothing survives).
Examples
Input: root = [5,2,8,1,3,6,9], low = 2, high = 6 Output: [5,2,6,null,3]
Nodes 1, 8 and 9 go, and 6 takes 8's place under 5.
Input: root = [4,2,6], low = 7, high = 9 Output: []
Every value is below 7, so nothing survives.
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output: [3,2,null,1]
The 0 goes and its right child 2 takes its place under 3; the 4 goes too.
Constraints
- The tree has between 1 and 10^4 nodes
- 0 <= Node.val <= 10^4
- All node values are distinct
- root is a valid binary search tree
- 0 <= low <= high <= 10^4
Approaches
- Rebuild from the surviving preorder — time O(n·h), space O(n)
Follow-up
The recursion uses O(h) stack; the spine walk needs O(1) extra space because each splice only replaces a child pointer. The use cases trim with only a lower bound and list the surviving values in order without building a tree.
Related problems
Start free on Cariara · Coding problems · System design studio
