Watch 10 video solutions for Construct Binary Tree from Preorder and Inorder Traversal, a medium level problem involving Array, Hash Table, Divide and Conquer. This walkthrough by take U forward has 309,952 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder and inorder consist of unique values.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.Problem Overview: You receive two arrays representing the preorder and inorder traversal of a binary tree. Your task is to reconstruct the original binary tree structure. Each value appears exactly once, which guarantees a unique tree.
Approach 1: Recursive Divide and Conquer with Hash Map (O(n) time, O(n) space)
The key observation: preorder traversal always gives you the root first, while inorder traversal tells you how the tree splits into left and right subtrees. Start with the first element in preorder as the root. Use a hash map to store each value's index in the inorder array so you can locate the root position in O(1) time. Everything to the left of that index belongs to the left subtree, and everything to the right belongs to the right subtree.
Recursively repeat the same process for each subtree. Maintain a pointer that advances through the preorder array as you build nodes. This technique works because preorder determines node creation order, while inorder determines subtree boundaries. Building the index map reduces repeated searches and keeps the total runtime at O(n) with O(n) extra space for recursion and the hash map.
This solution combines divide and conquer with a hash table to efficiently rebuild the structure of a binary tree. Most interview solutions use this exact pattern.
Approach 2: Iterative Stack Simulation (O(n) time, O(n) space)
An iterative version simulates the recursive construction using a stack. Start by creating the root from the first preorder value and push it onto the stack. Traverse the preorder array and keep attaching nodes as left children until the current node matches the inorder pointer. Once a match occurs, pop nodes from the stack while values align with inorder, then attach the next node as a right child.
The stack represents the path of ancestors whose right subtree has not yet been constructed. The inorder pointer acts as a signal telling you when a subtree is finished. Each node is pushed and popped at most once, so the algorithm runs in O(n) time and uses O(n) stack space.
Recommended for interviews: The recursive hash map approach is the standard solution interviewers expect. It clearly demonstrates understanding of preorder vs inorder properties and divide-and-conquer reasoning. The iterative stack approach is also strong because it avoids recursion and shows deeper mastery of traversal mechanics.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Divide and Conquer with Hash Map | O(n) | O(n) | Most common interview solution. Clear logic using preorder for roots and inorder for subtree boundaries. |
| Iterative Stack Construction | O(n) | O(n) | Useful when avoiding recursion or demonstrating deeper understanding of traversal mechanics. |