A parcel depot files incoming bin codes into a binary routing rack. Filing starts at the root slot: a new code is compared against the code already occupying the current slot — it moves to the left slot if it is smaller, or the right slot if it is larger — and this continues until it reaches an empty slot, where it is filed permanently. Given the order in which a batch of bin codes originally arrived (building the rack up from empty, one code at a time) and one more code to file afterward, report every code stored in the rack once the new code has been filed, read off in breadth-first order (top level first, then left-to-right within each level).
Line 1: a single integer n, the number of originally arriving codes.
Line 2: n space-separated distinct integers, the codes in their arrival order.
Line 3: a single integer v, the new code to file. It is guaranteed that v does not equal any of the n arrival codes.
Print a single line: the rack's codes after filing v, in breadth-first order, space-separated.
Example 1
Input
4 4 8 2 12 6
Expected
4 2 8 6 12
Explanation
Filing 4, 8, 2, 12 in order builds: 4 at the root; 8 files right of 4 (8 >= 4); 2 files left of 4 (2 < 4); 12 files right of 8 (12 >= 4, then 12 >= 8). Now filing 6: 6 >= 4 so it moves right to 8, then 6 < 8 so it files as the left child of 8. Reading breadth-first: root 4, then its children 2 and 8, then their children 6 (left of 8) and 12 (right of 8), giving "4 2 8 6 12".
Example 2
Input
3 5 3 1 2
Expected
5 3 1 2
Explanation
Filing 5, 3, 1 in order builds a left-leaning chain: 5 at the root, 3 as its left child (3 < 5), 1 as the left child of 3 (1 < 5, then 1 < 3). Filing 2: 2 < 5 (go left to 3), 2 < 3 (go left to 1), 2 >= 1 (file as the right child of 1, an empty slot). Breadth-first reading: 5, then 3, then 1, then 2, giving "5 3 1 2".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →