Keep Only a Range of a Search Tree

Medium

You are given the root of a binary search tree and bounds lo and hi. Remove every node whose value lies outside the interval [lo, hi]. The remaining nodes must keep their relative layout: if node x was a descendant of node y and both stay, x is still a descendant of y. Such a tree is unique. Return its root, which may differ from the original one; if no nodes remain, return an empty tree.

Example 1

root=tree_node([8, 3, 12, 1, 6, 10, 15]), lo=4, hi=11 → [8, 6, 10]

3 and 1 are below 4, so 3's right child 6 moves up into its place. 12 and 15 are above 11, so 10 takes 12's place. What's left is 8 with children 6 and 10.

Example 2

root=tree_node([5, 2, None, None, 4]), lo=3, hi=9 → [5, 4]

Only 2 is dropped, and its right child 4 becomes the left child of 5.

Example 3

root=tree_node([7, 2, 9]), lo=10, hi=20 → None

No value falls in the range, so the tree is empty.

Constraints

The tree has 1 to 10⁴ nodes
0 ≤ node value ≤ 10⁴, all values are distinct
root is a valid binary search tree
0 ≤ lo ≤ hi ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium K-th Smallest in a Search Tree Medium Biggest Search Subtree Medium Add Every Bigger Key Medium

Input

root=tree_node([8, 3, 12, 1, 6, 10, 15]), lo=4, hi=11

Expected

[8, 6, 10]

Run checks the first 3 tests in your browser. Submit checks all 30 tests on the server, hidden ones included.