A records vault stores n document ids in strictly increasing order, one per shelf slot. To make future lookups fast, the archivist builds a balanced binary search index over these ids using a fixed recursive rule: for any contiguous range of ids, the index node for that range is the id at the lower of the two middle positions of the range (when the range has an even number of ids, take the earlier of the two middle ones); every id before that position recursively forms the node's left branch, and every id after it recursively forms the node's right branch. A range with no ids contributes no node.
Before trusting a freshly built index, an auditor replays it: visit a node, then everything in its left branch, then everything in its right branch, starting from the root of the whole index. Given the sorted ids, report this replay order (the preorder scan) exactly as the auditor would record it.
Example 1
Input
5 1 2 3 4 5
Expected
3 1 2 4 5
Explanation
The full range [1,2,3,4,5] has 5 ids; its lower-middle position is index 2 (0-indexed), so the root of the index is 3. The left branch covers [1,2]: its lower-middle position is index 0, so 1 is that node, with 2 forming its right branch. The right branch covers [4,5]: its lower-middle position is index 0 of that sub-range, so 4 is that node, with 5 forming its right branch. Scanning root, then left branch, then right branch gives 3, then 1, 2, then 4, 5 — i.e. 3 1 2 4 5.
Example 2
Input
4 10 20 30 40
Expected
20 10 30 40
Explanation
With 4 ids, the lower-middle position of the full range is index 1, so the root is 20. Its left branch is just [10], forming a single node with no children. Its right branch is [30,40]: the lower-middle position there is index 0 of that sub-range, so 30 is that node with 40 as its right branch. The preorder scan is therefore 20, 10, 30, 40.
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 →