Remove nodes from a BST so that every remaining value lies within a given inclusive range.
Trim a Binary Search Tree
gfgYou are given the root of a binary search tree and two integers, low and high. Remove every node whose value is outside the inclusive range [low, high].
After trimming, the tree must still satisfy the binary search tree property, and the relative structure of the remaining nodes should be preserved as much as possible. In other words, when a node is removed, reconnect its valid children in the only way that keeps the result a BST.
Input Format
root: the root node of a binary search treelow: lower bound of the allowed rangehigh: upper bound of the allowed range
Output Format
Return the root of the trimmed binary search tree.
Constraints
- The input tree is a valid binary search tree.
- All node values are integers.
low <= high.- Keep only nodes with values in the range
[low, high].
Example 1
Input
root = [1,0,2], low = 1, high = 2
Output
[1,null,2]
Explanation
Node 0 is smaller than low, so it is removed. The remaining nodes 1 and 2 form a valid BST.
Example 2
Input
root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output
[3,2,null,1]
Explanation
Values 0 and 4 are outside the range and are removed. Their valid descendants are kept and reattached where appropriate.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.