Trim Binary Search Tree
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.
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:
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:
TreeNode of the trimmed Binary Search Tree. If no nodes remain within the range, return null.root is null, your function should return null.low <= high will always hold true.Examples
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.
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.
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
[0, 10^4].0 <= Node.val <= 10^9.0 <= low <= high <= 10^9.Loading editor...