Construct Binary Search Tree from Preorder Traversal
Construct Binary Search Tree from Preorder Traversal is a medium trees & bst problem solved with the tree serialization / deserialization pattern.
The best approach, optimal (single pass with an upper bound), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from insert one by one up.
Problem
Given the preorder traversal of a BST, rebuild the tree and return its root.
Examples
Example 1
- Input
preorder = [8, 5, 1, 7, 10, 12]- Output
[8, 5, 10, 1, 7, null, 12]
Example 2
- Input
preorder = [1, 3]- Output
[1, null, 3]
Constraints
1 <= n <= 100; values are unique and form a valid BST preorder.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Insert one by one | O(n²) | O(h) |
| Optimal (single pass with an upper bound) | O(n) | O(h) |
1Insert one by one
O(n²)Each insert is O(h), and h can be n.O(h)Insert each value into a BST in preorder order. Inserting in preorder rebuilds exactly the original tree.
- root = null; for each v: root = insert(root, v).
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root = null;
for (int v : preorder) root = insert(root, v);
return root;
}
private TreeNode insert(TreeNode n, int v) {
if (n == null) return new TreeNode(v);
if (v < n.val) n.left = insert(n.left, v);
else n.right = insert(n.right, v);
return n;
}
}class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
root = None
for v in preorder:
root = self.insert(root, v)
return root
def insert(self, n: Optional[TreeNode], v: int) -> TreeNode:
if n is None:
return TreeNode(v)
if v < n.val:
n.left = self.insert(n.left, v)
else:
n.right = self.insert(n.right, v)
return nclass Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
TreeNode* root = nullptr;
for (int v : preorder) root = insert(root, v);
return root;
}
private:
TreeNode* insert(TreeNode* n, int v) {
if (n == nullptr) return new TreeNode(v);
if (v < n->val) n->left = insert(n->left, v);
else n->right = insert(n->right, v);
return n;
}
};function bstFromPreorder(preorder) {
let root = null;
for (const v of preorder) root = insert(root, v);
return root;
}
function insert(n, v) {
if (n === null) return new TreeNode(v);
if (v < n.val) n.left = insert(n.left, v);
else n.right = insert(n.right, v);
return n;
}2Optimal (single pass with an upper bound)
O(n)O(h)Read preorder left to right with a shared index. build(bound) creates a node only if the next value is below bound. Its left subtree takes values below the node, and its right subtree takes values up to the parent's bound.
- If i == n or preorder[i] > bound, return null.
- root = new node(preorder[i++]).
- root.left = build(root.val); root.right = build(bound).
class Solution {
private int i;
public TreeNode bstFromPreorder(int[] preorder) {
i = 0;
return build(preorder, Integer.MAX_VALUE);
}
private TreeNode build(int[] p, int bound) {
if (i == p.length || p[i] > bound) return null;
TreeNode root = new TreeNode(p[i++]);
root.left = build(p, root.val);
root.right = build(p, bound);
return root;
}
}class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
self.i = 0
return self.build(preorder, 2**31 - 1)
def build(self, p: List[int], bound: int) -> Optional[TreeNode]:
if self.i == len(p) or p[self.i] > bound:
return None
root = TreeNode(p[self.i])
self.i += 1
root.left = self.build(p, root.val)
root.right = self.build(p, bound)
return rootclass Solution {
private:
int i;
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
i = 0;
return build(preorder, INT_MAX);
}
private:
TreeNode* build(vector<int>& p, int bound) {
if (i == (int)p.size() || p[i] > bound) return nullptr;
TreeNode* root = new TreeNode(p[i++]);
root->left = build(p, root->val);
root->right = build(p, bound);
return root;
}
};function bstFromPreorder(preorder) {
let i = 0;
function build(p, bound) {
if (i === p.length || p[i] > bound) return null;
const root = new TreeNode(p[i++]);
root.left = build(p, root.val);
root.right = build(p, bound);
return root;
}
return build(preorder, 2147483647);
}Edge cases to test
- Strictly increasing or decreasing input (skewed tree)
Hints
Hint 1
Each value you read must fit below an upper bound. If the next value is larger than the bound, this subtree is finished.
FAQ
What is the best time complexity for Construct Binary Search Tree from Preorder Traversal?
Optimal (single pass with an upper bound) runs in O(n) time and O(h) extra space.
Which pattern does Construct Binary Search Tree from Preorder Traversal use?
It is a trees & bst problem that uses the tree serialization / deserialization pattern. Other problems with the same pattern: Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Serialize and Deserialize Binary Tree.
Is there a brute force solution for Construct Binary Search Tree from Preorder Traversal?
Yes. Insert one by one takes O(n²) time and O(h) space. Insert each value into a BST in preorder order.
Which edge cases should I test for Construct Binary Search Tree from Preorder Traversal?
Strictly increasing or decreasing input (skewed tree).