Given the root of a binary search tree with distinct values and two integers lo <= hi, remove every node whose value is outside the range [lo, hi]. The remaining nodes must keep their relative order and the result must still be a search tree with the same ancestor relationships among the kept nodes. Return the root (None if nothing is left).
Examples
8 8
/ \ /
3 10 6
/ \ \ ==> / \
1 6 14 4 7
/ \ /
4 7 13
Input: root = build_tree([8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13]), lo = 4, hi = 9
Output: tree_to_list(...) == [8, 6, None, 4, 7]
Input: root = build_tree([1, 0, 2]), lo = 1, hi = 3
Output: [1, None, 2]
Constraints
0 <= number of nodes <= 1000-10**4 <= lo <= hi <= 10**4
Goals
- Use the ordering property to discard whole subtrees without visiting them
- Return the replacement subtree from each call