Trim a Binary Search Tree to a Range
Google● MediumFULLTIMEPHONE SCREENProblem statement
Given the root of a binary search tree and an inclusive range [low, high], remove every node whose value lies outside the range.
The relative structure of retained nodes must remain unchanged. Return the root of the trimmed tree; a retained descendant may become the new root.
Function
trimBST(root: TreeNode, low: int, high: int) → TreeNodeExamples
Example 1
root = [1,0,2]low = 1high = 2return = [1,null,2]Node 0 is below the interval and is removed.
Example 2
root = [3,0,4,null,2,null,null,1]low = 1high = 3return = [3,2,null,1]The branch rooted at 4 is above the interval. The valid descendants from the left branch remain attached in BST order.
Example 3
root = [0,null,1]low = 1high = 2return = [1]The original root is too small, so its retained right child becomes the new root.
Constraints
0 <= number of nodes <= 10^5.-10^9 <= node.val, low, high <= 10^9.low <= high, and all node values are distinct.- The input is a valid binary search tree.