Cut a tree down to a range
Remove every node whose value lies outside a given range from a search tree, keeping the others in place, by discarding whole sides when a node is out of range. About 14 minutes.
Out of range means skip a side
Suppose the allowed range is from low to high. If the current node is smaller than low, it must go. And since everything on its left is even smaller, that whole side must go too. The only thing that may survive is the right subtree, after trimming.
So replace the node by the trimmed version of its right subtree. A node bigger than high is handled as a mirror image, using its left subtree.
if root.val < low:
return trim_bst(root.right, low, high)
if root.val > high:
return trim_bst(root.left, low, high)- range
- 2 to 5
5 is in range. Keep it and trim both sides.
In range means keep it
A node inside the range stays. Its left and right children may still need trimming, so replace each child by the trimmed version of itself, and return the node.
An empty tree stays empty. Because each call returns the new top of its subtree, a parent just stores whatever its child call returned, and dropped nodes simply lose their links.
root.left = trim_bst(root.left, low, high) root.right = trim_bst(root.right, low, high) return root
A node is smaller than the lowest allowed value. Where can survivors be?
- AOnly in its right subtree
- BOnly in its left subtree
- CIn both subtrees
Show the answer
Only in its right subtree. Everything in its left subtree is smaller still.
Trim a search tree
Given the root of a binary search tree and two integers low and high, trim the tree so that all of its values are in the range from low to high, both included. Trimming must not change the relative structure of the nodes that stay: a node that stays keeps its descendants that stay. Return the root of the trimmed tree, which may be a different node from the original root.
root = [5, 3, 6, 2, 4, null, 7], low = 2, high = 5 → [5, 3, null, 2, 4]
0 ≤ number of nodes ≤ 10,000 · 0 ≤ node.val ≤ 10,000 · low ≤ high