Skip to content
MediumTreesAI interview only

Trim A Binary Search Tree

Asked atamazonmicrosoftgooglebloomberg

01 · Problem

You are given the root of a binary search tree (BST) with distinct values and two integers low and high. Remove every node whose value lies outside the inclusive range [low, high] and return the root of the trimmed tree.

The remaining nodes must keep their relative structure: if a node stays in the tree, any surviving descendant must remain its descendant. When a node is removed, its surviving subtree is attached in its place (this makes the result unique). The root of the answer may differ from the original root. If no node survives, return an empty tree. Trees are given and returned in level-order form, with null marking missing children (trailing nulls omitted).

02 · Examples

Example 01
Input
root = [1,0,2], low = 1, high = 2
Output
[1,null,2]

Node 0 is below the range and is removed; 1 and 2 remain.

Example 02
Input
root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output
[3,2,null,1]

Node 0 is removed and its surviving subtree (2 with left child 1) takes its place under 3. Node 4 exceeds high and is removed.

Example 03
Input
root = [2,1,3], low = 4, high = 9
Output
[]

Every value is below 4, so the trimmed tree is empty.

03 · Constraints

  • 01The number of nodes in the tree is in the range [0, 104].
  • 020 <= Node.val <= 104
  • 03All node values are unique, and the input is a valid binary search tree.
  • 040 <= low <= high <= 104

04 · Optimal complexity

Time
O(n)
Space
O(h)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem