Trim a Binary Search Tree

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree with distinct values and two integers low and high with low <= high. Remove every node whose value falls outside the inclusive range [low, high] and return the root of what remains. Trimming must keep the relative structure of the surviving nodes: if a kept node was a descendant of another kept node before trimming, it must still be a descendant afterwards. Under that rule the trimmed tree is unique. The root of the result may differ from the original root, and the result may be empty ([]). A recursive solution runs in O(n) time: when a node is too small, its whole left subtree is too small as well, and symmetrically for nodes that are too large.

Examples

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
Node 0 is below the range and is removed.
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]
0 is removed and its right subtree (2 with child 1) takes its place; 4 is removed.

Constraints

  • 1 <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^4
  • All values are distinct and form a valid BST
  • 0 <= low <= high <= 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems