Construct Binary Search Tree from Preorder Traversal Solution
Construct Binary Search Tree from Preorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Construct Binary Search Tree from Preorder Traversal is a medium coding problem on arrays, binary search and trees, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Trees, Stack, Monotonic Stack
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array preorder of distinct integers that is the preorder traversal of a binary search tree — each node listed before its left subtree, which comes before its right subtree. Rebuild the tree and return its root.
In a binary search tree every value in a node's left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly larger. It is guaranteed that preorder describes such a tree, and that tree is unique.
Example 1
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Explanation: 8 is the root; 5, 1, 7 are smaller and form its left subtree (5 with children 1 and 7); 10, 12 are larger and form the right subtree.
Example 2
Input: preorder = [1,3]
Output: [1,null,3]
Explanation: 3 is larger than the root, so it is the root's right child.
Example 3
Input: preorder = [3,2,1]
Output: [3,2,null,1]
Explanation: Each value is smaller than the one before it, so the tree is a chain going left.
Constraints
1 <= preorder.length <= 1001 <= preorder[i] <= 1000All the values of preorder are unique
Hints for Construct Binary Search Tree from Preorder Traversal
Hint 1
The first value is the root. The values after it that are smaller form the left subtree's preorder, and the rest the right subtree's.
Hint 2
Splitting by scanning for the first larger value is O(n^2) on a chain. Instead, build while reading: pass down an upper bound for the current subtree.
Hint 3
build(bound): if the next value exceedsbound, this subtree is empty. Otherwise take it as the node, build its left subtree with the boundnode.val, then its right subtree with the inheritedbound.
How to solve Construct Binary Search Tree from Preorder Traversal
Read the preorder array once with a shared index. Each recursive call builds the largest subtree whose values stay below an upper bound; the bound tells it exactly when its subtree has ended, so no searching is needed.
Approach
- Keep an index
i = 0intopreorder. build(bound): ifiis past the end orpreorder[i] > bound, return null.- Otherwise create a node with
preorder[i], advancei, setleft = build(node.val)andright = build(bound), and return the node. - Return
build(+infinity)(the largest 32-bit integer works).
Why it works
In preorder, a node is followed first by all of its left subtree (values below it) and then by its right subtree (values above it but below the bound inherited from the nearest ancestor it hangs left of). The first value that breaks the bound is therefore the first value outside the current subtree, so each call consumes exactly its subtree's values.
Complexity
- Time —
O(n) — every value is consumed once - Space —
O(h) for the recursion
Pitfalls
- The left subtree's bound is the node's value; the right subtree inherits the parent's bound, not the node's value.
- Keep the index shared across calls (a field, a reference or a one-element array), not a copy.
- Inserting each value from the root also works but is O(n^2) on a sorted input.
Reference solution
Python
from typing import List, Optional
def bstFromPreorder(preorder: List[int]) -> Optional[TreeNode]:
i = 0
def build(bound):
nonlocal i
if i == len(preorder) or preorder[i] > bound:
return None
node = TreeNode(preorder[i])
i += 1
node.left = build(node.val)
node.right = build(bound)
return node
return build(float("inf"))Java
public static TreeNode bstFromPreorder(int[] preorder) {
return build(preorder, new int[1], Integer.MAX_VALUE);
}
static TreeNode build(int[] pre, int[] i, int bound) {
if (i[0] == pre.length || pre[i[0]] > bound) return null;
TreeNode node = new TreeNode(pre[i[0]++]);
node.left = build(pre, i, node.val);
node.right = build(pre, i, bound);
return node;
}C++
TreeNode* buildBounded(vector<int>& pre, int& i, int bound);
TreeNode* bstFromPreorder(vector<int>& preorder) {
int i = 0;
return buildBounded(preorder, i, INT_MAX);
}
TreeNode* buildBounded(vector<int>& pre, int& i, int bound) {
if (i == (int) pre.size() || pre[i] > bound) return nullptr;
TreeNode* node = new TreeNode(pre[i++]);
node->left = buildBounded(pre, i, node->val);
node->right = buildBounded(pre, i, bound);
return node;
}JavaScript
var bstFromPreorder = function(preorder) {
var i = 0;
var build = function(bound) {
if (i === preorder.length || preorder[i] > bound) return null;
var node = new TreeNode(preorder[i++]);
node.left = build(node.val);
node.right = build(bound);
return node;
};
return build(Infinity);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search