450. Trim a Binary Search Tree
You are given the root of a binary search tree plus two integers low and high with low <= high. Remove every node whose value falls outside the closed range [low, high], and return the root of what remains.
The trimming must not rearrange anything that survives: if a surviving node was a descendant of another surviving node before, it still is afterwards. Because the input is a BST, there is exactly one correct result — you never have to invent a new layout.
The function receives the root node and the two bounds, and returns the root of the trimmed tree (possibly a different node than the original root, or no tree at all).
Example 1:
Input: root = [3, 0, 4, null, 2, null, null, 1], low = 1, high = 3
Output: [3, 2, null, 1]
Explanation: 0 and 4 fall outside [1, 3]. Dropping 0 promotes its right child 2 (along with 2's child 1) into the root's left slot, and dropping 4 leaves the root without a right child.
Example 2:
Input: root = [1, 0, 2], low = 1, high = 2
Output: [1, null, 2]
Explanation: Only the left child 0 is out of range. It has no children to promote, so the root simply loses its left subtree.
Constraints:
- 1 ≤ number of nodes ≤ 3000
- 0 ≤ Node.val ≤ 10⁴
- All node values are unique and the input is a valid BST.
- 0 ≤ low ≤ high ≤ 10⁴
Hints:
Use the BST ordering to discard whole subtrees at once: if a node's value is below low, every value in its left subtree is below low too — the only place survivors can hide is its right subtree. Mirror that for values above high.
Write the function with the contract 'return the trimmed version of this subtree'. Out-of-range node: forward the call to the one side that can survive. In-range node: keep it, and re-point its left and right at the trimmed versions of its children.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 0, 4, null, 2, null, null, 1], low = 1, high = 3
Expected output: [3, 2, null, 1]