Trim a Binary Search Tree to a Range

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) → TreeNode

Examples
Example 1
root = [1,0,2]
low = 1
high = 2
return = [1,null,2]
Node 0 is below the interval and is removed.
Example 2
root = [3,0,4,null,2,null,null,1]
low = 1
high = 3
return = [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 = 1
high = 2
return = [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.

The trick is using the BST ordering to skip work. At each node, there are three cases. If node.val < low, the node and its entire left subtree are out, so return trim(node.right). If node.val > high, the node and its right subtree are out, so return trim(node.left). Otherwise the node stays, and you set left = trim(left) and right = trim(right). Return the node. The common pitfall is trimming both children no matter what, or forgetting that the returned subtree replaces the node, which is how Example 3 gets a new root. Another pitfall is recursion depth. With 10^5 nodes and a skewed tree, recursion can overflow in some languages, so know the iterative version. Time is O(n), space is O(h). If you blank during the live OA, StealthCoder can supply the recursion while you read the cases.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.