Trim a Search Tree to a Window
MediumTrees
Problem
Given a binary search tree of distinct values and an inclusive window [lo, hi], remove every node whose value lies outside the window.
Every surviving node must keep its relative ancestry: if a was an ancestor of b before and both survive, a is still an ancestor of b. This makes the result unique. Return the new root (possibly empty).
Example 1
- Input:
- root = [1, 0, 2], lo = 1, hi = 2
- Output:
- [1, null, 2]
Example 2
- Input:
- root = [3, 0, 4, null, 2, null, null, 1], lo = 1, hi = 3
- Output:
- [3, 2, null, 1]
0 is too small, so its right subtree (2 with child 1) moves up into its place; 4 is too large and has no left subtree.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- 0 ≤ node.val ≤ 10^4
- 0 ≤ lo ≤ hi ≤ 10^4
- The tree height is at most 500.
Hint
Show the first hint
If a node's value is below lo, can anything in its left subtree survive?
Walkthrough
How to approach it
01Clarify before coding
- Is the window inclusive? Yes.
- Can the root itself be removed? Yes, the returned root may be a different node or empty.
- May I reuse the nodes? Yes, relinking existing nodes is expected.
02Brute force
Collect the in-range values and rebuild a search tree from them.
Cost: O(n log n) or O(n), but rebuilding does not preserve the required ancestry, so the shape is wrong.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.