Construct Binary Search Tree from Preorder Traversal

Given an integer array preorder — the preorder traversal of a binary search tree with distinct values — construct the BST and return its root.

The tree is returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

For a BST, preorder alone determines the tree — the ordering replaces inorder.

Simplest: insert each preorder value into the BST in order.

O(n): keep a monotonic stack — smaller value is the top's left child; larger value pops to its parent's right.

Common doubts

A BST's ordering tells you which side each value belongs on, so you don't need inorder to disambiguate.

The LAST node popped while the top is smaller than v — v becomes its right child.

A sorted (or reverse-sorted) preorder builds a degenerate chain, making inserts O(n) each — O(n^2) overall.

Interview follow-ups

· What an interviewer asks next.

Yes — recurse with an upper bound: build a node only while the next value is below the bound, giving O(n) without an explicit stack.

For a general tree you need both; a BST needs only preorder because ordering is the implicit second traversal.

Fun facts

A BST is uniquely determined by its preorder (or its postorder) alone — a property general binary trees don't share.
The monotonic-stack build is the same shape as 'next greater element' — ancestors are popped when a larger value arrives.

Asked at

AmazonMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: preorder = [8, 5, 1, 7, 10, 12]
Output: [8, 5, 10, 1, 7, null, 12]
Root 8; 5 and 10 are its children; 1, 7 under 5; 12 under 10.

Example 2

Input: preorder = [1, 3]
Output: [1, null, 3]
3 > 1, so it's the right child.

Constraints

- 1 <= preorder.length <= 100 - 1 <= preorder[i] <= 10^8 - All values are unique - preorder is a valid preorder of a BST

A BST is special: preorder alone determines it (no inorder needed), because the ordering tells you where each value goes. The simplest build inserts each value into the BST in order. The slick O(n) build uses a monotonic stack that tracks the chain of ancestors a new value can attach under.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST insert. Descend left/right by comparison to place a value.

Preorder. Node before its subtrees — the first value is the root.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Why is preorder enough for a BST?”

The ordering acts as the second traversal — you always know which side a value belongs on.

“Values distinct?”

Yes.

The ideal opening — say it like this

For a BST, preorder alone is enough because the ordering tells me left vs right, so I can insert each value in turn.

For O(n) I keep a stack of ancestors: a smaller value is the left child of the top, a larger value pops until it finds the parent whose right child it becomes.

Understand the problem

Worked example — preorder = [8, 5, 1, 7, 10, 12]

8 root. 5<8 -> left of 8. 1<5 -> left of 5.
7>1,7>5 pop 1,5 -> right of 5. 10>7,>8 pop 7,8 -> right of 8. 12>10 -> right of 10.
        8
       / \
      5   10
     / \    \
    1   7    12

Key observations

1Aha

Preorder determines a BST

The ordering replaces the need for inorder — the first value is the root and comparisons place the rest.

2Aha

Stack tracks candidate parents

The monotonic stack holds the ancestors a new value could attach under.

3Aha

Each node pushed/popped once

That's what makes the stack build O(n).

Brute force vs optimal

	Insert each value	Monotonic stack
Idea	BST-insert values one by one	Attach via a stack of ancestors
Time	O(n * height)	O(n)
Space	O(height)	O(n)

Both build the same BST; the stack version is linear. Full code is in the Approaches selector below.

Summary

Key takeaway

Preorder alone builds a BST. Insert each value (O(n·h)), or use a monotonic stack — smaller ⇒ left child of the top, larger ⇒ pop to the parent and become its right child (O(n)).

for v after the root:
    if v < top: top.left = v
    else: pop while top < v; last_popped.right = v
    push v