Trim a Binary Search Tree
mediumTrees & BST II+20 XPTime limit 2s
A library's catalogue is a binary search tree of book ids (all distinct). Only ids in the range lo..hi (inclusive) stay; every other node must be removed. When a node goes, its surviving descendants move up to take its place, so the tree stays a valid BST and every surviving node keeps the same relative arrangement (if a was an ancestor of b and both survive, a is still an ancestor of b). Print the trimmed tree.
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one BST, then a line lo hi.
Output: the trimmed tree in the same level-order format (null if nothing survives).
Constraints: 0 ≤ nodes ≤ 10⁴, distinct values between −10⁴ and 10⁴, −10⁴ ≤ lo ≤ hi ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: if a node's value is below lo, the node and its whole left subtree are gone — the answer is the trimmed right subtree. Symmetrically for values above hi. Otherwise keep the node and trim both children recursively.
Sample input 1
1 0 2 1 2
Sample output 1
1 null 2
Sample input 2
3 0 4 null 2 null null 1 1 3
Sample output 2
3 2 null 1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).