Frontend School

Trim Binary Search Tree

DSA
medium

Trim Binary Search Tree

Medium
Tree
Binary Search Tree
Recursion

Overview

In many real-world applications, such as managing a database of vehicle service records or driver ratings, data is often stored in a Binary Search Tree (BST) for efficient retrieval and updates. However, sometimes we only need to operate on a subset of this data, specifically records falling within a certain range. This problem challenges you to efficiently filter out irrelevant data from a BST.

What you need to do / Task

Your task is to implement a function trimBST that takes the root of a Binary Search Tree and two integers, low and high. The function should return the root of a new Binary Search Tree (or the modified original tree) such that all nodes in the resulting tree have values within the inclusive range [low, high].

Specifically, for any node node in the trimmed BST, it must satisfy low <= node.val <= high. The relative structure of the nodes that remain should be preserved, meaning if nodeA was the left child of nodeB in the original BST, and both remain, nodeA should still be the left child of nodeB in the trimmed BST.

Input & output

Input:

  • root: The root node of a Binary Search Tree. Each TreeNode has a val property (number), left (TreeNode or null), and right (TreeNode or null).
  • low: An integer representing the lower bound of the desired range (inclusive).
  • high: An integer representing the upper bound of the desired range (inclusive).

Output:

  • The root TreeNode of the trimmed Binary Search Tree. If no nodes remain within the range, return null.

Clarifications

  • If the input root is null, your function should return null.
  • You can assume low <= high will always hold true.
  • The input tree is guaranteed to be a valid Binary Search Tree.

Examples

1

Example 1

Input:

root = [1,0,2], low = 1, high = 2

Output:

[1,null,2]

Note:

Node 0 is less than low (1) and is removed. Node 1 and 2 are within the range and their relative structure is maintained.

2

Example 2

Input:

root = [3,0,4,null,2,null,null,1], low = 1, high = 3

Output:

[3,2,null,1]

Note:

Nodes 0 and 4 are outside the range [1, 3]. Node 1, 2, 3 are within. The trimmed tree should connect 1 to 2, and 2 to 3, preserving BST properties.

3

Example 3

Input:

root = [1], low = 1, high = 2

Output:

[1]

Note:

Node 1 is within the range [1, 2], so the tree remains unchanged.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • 0 <= Node.val <= 10^9.
  • 0 <= low <= high <= 10^9.
  • The tree is guaranteed to be a Binary Search Tree.

What interviewers evaluate

  • Correctness and Logic: Does the solution correctly identify and remove nodes outside the specified range while preserving BST properties?
  • Efficiency: Is the solution's time and space complexity optimal for the given constraints?
  • Edge Case Handling: Does the code gracefully handle scenarios like an empty tree or a range that excludes all nodes?
  • Code Quality: Is the code clean, well-structured, readable, and properly handles recursion (if applicable)?

Loading editor...