Trim a Binary Search Tree

Given the root of a binary search tree and the inclusive range [low, high], trim the tree so that all remaining node values lie inside the range. Pattern focus: BST Range Bounds. The BST property lets you discard entire subtrees that are completely outside the range while preserving the relative structure of the remaining nodes.

Input Format

root = binary tree root, low = lower bound, high = upper bound

Output Format

trimmed BST root

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root, low and high must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

[1,null,2]

Explanation:

Node 0 is removed because it is below the lower bound.

Example 2:

Input:

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

Output:

[3,2,null,1]

Explanation:

Nodes 0 and 4 are trimmed away, leaving only values inside the range.

Loading...
Trim a Binary Search Tree - Binary Search Tree