Trim a Binary Search Tree
Medium · Binary Search Trees · about 15 minutes
Asked at Amazon, Google, Meta, Bloomberg.
Prune a binary search tree so that only values within [low, high] remain, and return the new root. Nodes that survive keep their relative arrangement: if one surviving node was below another, it stays below it. There is only one correct result.