All problems

Trim a Binary Search Tree

Medium · tree dfs

You are given the root of a binary search tree (BST) and two integers low and high, with low <= high. In a BST, every value in a node's left subtree is smaller than the node's own value, every value in its right subtree is larger, and no value appears twice.

Remove every node whose value is outside the range [low, high]. Both ends of the range are allowed values. The nodes that stay are never reshuffled, only cut out: if a node's parent is removed, the node's new parent is its closest ancestor that stays, and it remains on the same side of that ancestor. Because of this rule there is exactly one possible result.

Return the root of the trimmed tree. The root itself can change if the old root is removed. If no node stays, return an empty tree.

Examples

Example 1

Input: root = [10, 5, 15, 3, 7, 12, 20], low = 5, high = 15

Output: [10, 5, 15, null, 7, 12]

3 and 20 are outside [5, 15] and are cut away. Every other node keeps its parent.

Example 2

Input: root = [10, 5, 15, 3, 7, 12, 20], low = 11, high = 14

Output: [12]

10 and 15 are removed. Of the nodes that stay, only 12 is in the range, so it becomes the new root.

Example 3

Input: root = [5, 1, 8], low = 6, high = 7

Output: []

Every value is outside the range, so nothing is left.

Constraints

• The number of nodes is in the range [0, 5000], and the height of the tree is at most 1000.
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• The tree is a valid binary search tree.
• -10^4 <= low <= high <= 10^4