Construct Binary Tree from Preorder and Inorder Traversal
The Prompt
Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.
Understanding the Problem
Each traversal alone is ambiguous, but together they pin the tree down. Preorder visits root-left-right, so its first element is always the root of the current subtree. Inorder visits left-root-right, so finding that root inside the inorder array splits it cleanly: everything to the left belongs to the left subtree, everything to the right to the right subtree.
That gives a recursive recipe: take the next preorder element as the root, locate it in inorder to learn the left subtree size, then recurse on the two inorder halves ā consuming preorder elements in order as roots.
The Interview Flow
Interviewer
How can you reconstruct a binary tree from its preorder and inorder traversals?
Candidate
The key is understanding what each traversal tells us. The first element of the preorder traversal is always the root of the (sub)tree. The inorder traversal shows the root with its left subtree elements to its left and its right subtree elements to its right.
Interviewer
How do you use that relationship?
Candidate
I can use a recursive approach. I take the first element from `preorder` as the current root. Then I find this root's value in the `inorder` array. This position in `inorder` splits the array into the left and right subtrees. The number of elements in the left part of `inorder` tells me how many elements from the preorder traversal belong to the left subtree.
Interviewer
How do you make the recursive calls?
Candidate
Once I know the size of the left subtree, I know which parts of the `preorder` and `inorder` arrays correspond to the left and right children. I can then make recursive calls with these smaller subarrays to build the left and right subtrees. To speed up finding the root's index in the `inorder` array, I can pre-process it into a hash map.
Interviewer
That's a solid recursive strategy. The hash map is a good optimization. Please proceed.
Why do the two traversals determine a unique tree?
The invariant: each recursive call receives the exact preorder and inorder slices of one subtree, with the subtree root sitting at the front of the preorder slice. The inorder split computes the left subtree size, and that size tells you precisely how to slice preorder for the two recursive calls ā so every node is placed exactly once and no ambiguity remains (this relies on values being unique).
With a hash map from value to inorder index, each root lookup is O(1), giving O(n) time and O(n) space for the map plus O(h) recursion. Without the map, each linear search costs O(n), degrading to O(nĀ²).
Recursive Divide and Conquer
- First, create a hash map from the `inorder` traversal to store each value and its index for O(1) lookups.
- Define a recursive helper function, `build`, that takes boundaries for the current `preorder` and `inorder` segments.
- The first element in the current `preorder` segment is the root of the current subtree. Create a new `TreeNode` with this value.
- Find this root value's index in the `inorder` map. This is `mid`.
- The elements to the left of `mid` in the `inorder` segment form the left subtree. The number of these elements is `numLeft = mid - inorder_start`.
- Recursively call `build` for the left subtree. The corresponding `preorder` segment is from `preorder_start + 1` for `numLeft` elements. The `inorder` segment is from `inorder_start` to `mid - 1`.
- Recursively call `build` for the right subtree. The `preorder` segment starts after the left subtree's elements. The `inorder` segment is from `mid + 1` to `inorder_end`.
- Link the returned left and right subtrees to the root and return the root.
- The base case for the recursion is when the start index is greater than the end index.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function buildTree(preorder, inorder) {
if (!preorder.length || !inorder.length) return null;
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
const mid = inorder.indexOf(rootVal);
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
return root;
}Explanation
Rebuild the tree from preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7], one root at a time.
1preorder[0] = 3 is the root. In inorder, 3 sits at index 1: [9] goes to the left subtree (size 1), [15, 20, 7] to the right (size 3).
2Next preorder element 9 becomes the left child ā its inorder slice [9] has nothing on either side, so it is a leaf. The following element 20 roots the right subtree; inorder [15, 20, 7] splits into [15] and [7].
3The last preorder elements 15 and 7 fill the singleton slices as leaves. All five preorder elements consumed in order ā the tree is uniquely rebuilt.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.