Mid/SeniorBinary Search Tree Binary Tree Depth-First Search Tree

Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high].

Trimming the tree should not change the relative structure of the elements that will remain in the tree; that is, any node's descendant should remain a descendant. It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1

        1                   1
       / \       ->          \
      0   2                   2

Inputroot = [1,0,2], low = 1, high = 2

Output[1,null,2]

The node with value 0 is outside the range [1, 2], so it is removed while preserving the remaining structure.

Example 2

        3                 3
       / \               /
      0   4     ->      2
       \               /
        2             1
       /
      1

Inputroot = [3,0,4,null,2,null,null,1], low = 1, high = 3

Output[3,2,null,1]

Values outside [1, 3] are removed, leaving 3 as the root with 2 as its left child and 1 as a descendant.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^4
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 10^4

Trim a Binary Search Tree

Constraints

Asked at 5 companies

Your Solution

Switching Language

AI code evaluation