Construct BT from Preorder and Inorder
Rebuild the unique binary tree from its preorder and inorder traversals.
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of inorder also appears in preorder.
- preorder is guaranteed to be the preorder traversal of the tree.
- inorder is guaranteed to be the inorder traversal of the tree.
Intuition
To construct bt from preorder and inorder traversals, you need what each one contributes. Neither is sufficient alone — many different trees share an inorder sequence — but together they identify exactly one tree.
Preorder visits the node before its subtrees, so its first element is always the root. That is handed to you for free.
Inorder visits left, node, right. Once you know the root's value, locating it in the inorder sequence splits that sequence in two: everything before it is the left subtree, everything after is the right. The split also reveals the sizes of both subtrees, and those sizes tell you how to divide the preorder range to match — the next k preorder elements are the left subtree when the inorder split puts k values on the left.
So the recursion is: take the root from the front of preorder, split inorder around it, and recurse on both halves.
Two details keep it linear. Scanning inorder for the root each time would make it O(n²), so precompute a value-to-index map. And passing array slices copies data at every level; passing index bounds instead keeps each call O(1) in space. With a single forward-moving preorder pointer, the left subtree is built before the right, which is the natural order preorder supplies.
To construct binary tree from preorder and inorder traversal, preorder hands you roots in order; inorder tells you where each root splits its subtree. The hash map from value to inorder index turns the "find the root" step from a linear scan into O(1), which is the difference between O(n²) and O(n).
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(n) space.
Index the inorder values once
Build a hash map from value to inorder index before recursing. Without it every call scans to find the root and the build degrades to O(n²). This assumes values are unique, which the problem guarantees.
Take the root from the front of preorder
Keep a pointer starting at index 0 of the preorder array. The value there is the current subtree's root. Create the node, then advance the pointer so the next call receives the next root in sequence.
Split the inorder range around the root
Look up the root's index in the map. Values to its left form the left subtree, values to its right form the right. Pass index bounds rather than slicing — slicing copies arrays and turns a linear algorithm quadratic.
Build left before right
Recurse on the left range first, then the right. Preorder lists the entire left subtree before the right, so the shared pointer naturally hands each call its correct root. Reversing the order desynchronises the pointer and builds the wrong tree.
Stop on an empty range
When the left bound passes the right bound the range holds no nodes, so return null without consuming anything. This terminates every branch and handles an empty input without a separate check.
Cost of the reconstruction
Each node is created once and each root lookup is O(1) through the map, giving O(n) time. Space is O(n) for the map plus O(h) for the recursion stack — O(log n) balanced, O(n) for a degenerate chain.
Solution & live demo
Common pitfalls
Searching the inorder array each time
mid = inorder.index(val)
idx = {v: i for i, v in enumerate(inorder)}
... idx[val]A linear search at every node makes the build O(n²), which times out on a skewed tree of 3,000 nodes. Precomputing positions once makes each lookup constant.
Passing the preorder index by value
def build(lo, hi, pre):
val = preorder[pre]
node.left = build(lo, mid - 1, pre + 1)self.pre = 0 ... val = preorder[self.pre]; self.pre += 1
The left subtree consumes an unknown number of preorder entries, so the right subtree's starting index isn't pre + 1 — it depends on how many nodes the left call used. A shared cursor advances correctly without that arithmetic.
Building the right subtree first
node.right = build(idx[val] + 1, hi) node.left = build(lo, idx[val] - 1)
node.left = build(lo, idx[val] - 1) node.right = build(idx[val] + 1, hi)
Preorder lays out root, then the entire left subtree, then the right. A shared cursor must consume them in that same order, so left has to be built first — the opposite of the postorder variant.
Edge cases
One side of every split is empty; recursion depth n.
Problem guarantees uniqueness — the split would be ambiguous otherwise.