Construct Binary Search Tree from Preorder Traversal
Build the binary search tree whose preorder traversal is given, in a single pass, by passing each recursive call an upper bound for the values its subtree may take.
Problem Understanding
Construct Binary Search Tree from Preorder Traversal: given an array of distinct integers that is the preorder traversal of a BST, build that tree and return its root.
Examples: [8,5,1,7,10,12] → [8,5,10,1,7,null,12]; [1,3] → [1,null,3].
The Intuition: Each Subtree Ends at Its Bound
Preorder is root, left subtree, right subtree. The left subtree is every following value smaller than the root; the right subtree is everything after that, up to the parent's own limit:
- Read values left to right with one shared index.
- A subtree with bound b takes the next value only if it is below b; otherwise it is empty.
- Left child: bound = node's value. Right child: bound = the parent's bound.
It is the preorder traversal run backwards, and the bound idea is the one in Validate Binary Search Tree. The general case needs inorder too: Construct Binary Tree from Preorder and Inorder Traversal.
Interactive Walkthrough
A SUBTREE TAKES THE NEXT VALUE ONLY IF IT IS BELOW ITS BOUND
BOUND = ∞
preorder
i
root = null
bound
:
next
8
built
0
Read the preorder [8,5,1,7,10,12] left to right; the root's subtree takes every value below ∞
Next
8 < ∞: make it a node. Its left subtree takes values below 8, its right subtree values below ∞
preorder
The preorder array is on top with the next value marked; the tree grows below. Watch the bound readout decide when a subtree stops. Try Decreasing for a left chain.
Dry Run Table
Input: [8,5,1,7,10,12].
| Value | Bound | Becomes |
|---|---|---|
| 8 | ∞ | root |
| 5 | 8 | left of 8 |
| 1 | 5 | left of 5 |
| 7 | 8 | right of 5 (7 is not below 1 or 5) |
| 10 | ∞ | right of 8 (not below 8) |
| 12 | ∞ | right of 10 |
Answer: [8,5,10,1,7,null,12].
The Solution Template
One index, one bound per call.
Construct Binary Search Tree from Preorder Traversal Code
1var bstFromPreorder = function(preorder) {2 let i = 0;3 const build = (bound) => {4 if (i === preorder.length || preorder[i] > bound) return null;5 const node = new TreeNode(preorder[i++]);6 node.left = build(node.val);7 node.right = build(bound);8 return node;9 };10 return build(Infinity);11};
Edge Cases & Common Mistakes
- One value: a single node.
- Decreasing values: a left chain; recursion depth n.
- Increasing values: a right chain.
- Searching for the split each time: finding the first larger value with a scan makes it O(n²); the shared index avoids that.
- Forgetting to reset the shared index (static or field) between calls.
Summary
Read preorder with one index; build(bound) returns null when the next value is not below bound, otherwise makes a node and builds its left (bound = value) and right (bound = parent's bound) subtrees. O(n) time, O(h) space.
More practice: DSA interview questions with answers · patterns cheat sheet