Skip to main content

BST Trim to Value Window

medium
Binary Search TreeTreeDepth First SearchBinary TreeRecursionDfs Recursive
Asked atAmazonGoogleUber

Problem Description

Given the `root` of a **Binary Search Tree** and two integers `loBound` and `hiBound` (where `loBound <= hiBound`), **trim** the tree so that all node values lie within the closed range `[loBound, hiBound]`. Return the root of the trimmed tree.

The trimming must preserve the BST structure. Nodes outside the range should be removed, and their children that remain in range should be re-attached to the tree correctly.

**Example 1:**
```
5
/ \
2 8
/ \
1 3
```
Input: root = [5, 2, 8, 1, 3], loBound = 2, hiBound = 6
Output: [5, 2, null, null, 3]
Explanation: Node 8 is removed (8 > 6). Node 1 is removed (1 < 2).

**Example 2:**
```
9
/ \
4 13
/ \
2 7
```
Input: root = [9, 4, 13, 2, 7], loBound = 4, hiBound = 9
Output: [9, 4, null, null, 7]
Explanation: Node 13 is removed (13 > 9). Node 2 is removed (2 < 4).

Constraints

  • The number of nodes in the tree is in the range [1, 10000].
  • Node values are in the range [-10^5, 10^5].
  • All node values are unique.
  • loBound <= hiBound.

Follow-up

Can you implement this iteratively without recursion to handle extremely deep skewed trees without stack overflow?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.