Show problems as
Classic problem #1008MediumArrayStackTreeBinary Search TreeMonotonic StackBinary Tree

Construct Binary Search Tree from Preorder Traversal

Real-world version: Rebuild the Accession Index
Tracked in this browser only
Read Construct Binary Search Tree from Preorder Traversal on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A museum files its specimens in a branching index. Each card in the index carries one accession number and hangs at most two cards below it, one on the low side and one on the high side. The filing rule holds everywhere in the index: every number hanging anywhere below a card on its low side is smaller than that card's number, and every number hanging anywhere below it on its high side is larger. All the numbers are different.

A curator read the index out into entries in card-first order: she wrote down a card's number, then the whole of what hangs on its low side, then the whole of what hangs on its high side, applying that same order at every card she reached. entries[0] is therefore the topmost card.

Rebuild the index and return it as a band listing, one band of the index at a time from the top down, left to right within a band. Slot 0 holds the topmost card. Each card that appears in the listing takes the next two unclaimed slots for what hangs below it, the low side first and the high side second. A slot holding null means nothing hangs there, and such a slot claims no slots of its own. Slots that would hold null at the very end of the listing must be left off.

Exactly one index matches a given card-first reading, so the listing is unique.

Examples

Example 1

Input
entries = [9, 4, 2, 6, 15, 20]
Output
[9, 4, 15, 2, 6, null, 20]

The topmost card is 9. The reading covers all of its low side next, namely 4 with 2 below on the low side and 6 below on the high side, and only then its high side, namely 15 with 20 hanging high of it.

Example 2

Input
entries = [3, 2, 1]
Output
[3, 2, null, 1]

Each number read is smaller than the one before it, so every card hangs on the low side of the card just read, and the index is a single chain down the low side.

Example 3

Input
entries = [1]
Output
[1]

One card and nothing hanging below it, so the listing has a single slot.

Example 4

Input
entries = [50, 30, 20, 40, 70, 60, 80]
Output
[50, 30, 70, 20, 40, 60, 80]

The index comes out full to three bands: 50 on top, then 30 and 70, then 20, 40, 60 and 80.

Example 5

Input
entries = [4, 2, 1, 6, 5, 7]
Output
[4, 2, 6, 1, null, 5, 7]

Card 2 has 1 on its low side and nothing on its high side, so the slot for that high side sits in the middle of the listing holding `null`.

Constraints

  • 1 <= entries.length <= 100
  • 1 <= entries[i] <= 1000
  • All the values of entries are unique.
  • entries is the card-first reading of some index obeying the filing rule.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def bst_from_preorder(entries: list[int]) -> list[int | None]:
Java
public Integer[] bstFromPreorder(int[] entries)

More on the same topics