513. Trim to the Range
A weather station logs temperature readings in a binary search tree. Only readings between low and high, both inclusive, are trustworthy, so every other reading must be dropped.
Remove every node of root whose key lies outside [low, high] and return the root of the remaining tree. Nodes that stay must keep their original ancestor and descendant relationships among themselves, so the shape of the result is uniquely determined and it is still a search tree. If no key lies inside the range, return an empty tree.
Example 1
- Input:
- root = [8,3,12,1,5,10,15], low = 4, high = 11
- Output:
- [8,5,10]
- Explanation:
Key 3 is below 4 so its right child 5 takes its place, key 12 is above 11 so its left child 10 takes its place, and keys 1 and 15 vanish: [8,5,10].
Example 2
- Input:
- root = [20,10,30], low = 25, high = 40
- Output:
- [30]
- Explanation:
The root 20 and its left child 10 are below 25, so only the node 30 survives.
Constraints
0 ≤ number of nodes ≤ 104
-1000 ≤ node key, low, high ≤ 1000, and low ≤ high
All keys are distinct and root is a valid binary search tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(1)