Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.