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.
This approach uses recursion to build the tree. We know that the first element of the preorder traversal is the root of the tree. We find that element in the inorder traversal to determine the elements of the left and right subtrees. We then recursively build the left and right subtrees.
Steps:
This Python solution defines a TreeNode class and constructs the tree using a helper function. The helper function takes indices to track the ranges in the preorder and inorder lists, creating new TreeNode objects as necessary and using an index map for efficient lookups. This approach recursively builds the tree, taking care of each node's left and right subtrees.
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is processed once.
Space Complexity: O(n) for the recursion call stack and additional structures.
This approach uses an iterative method to build the binary tree using stacks. By leveraging the properties of the preorder and inorder sequences, we can keep track of the tree nodes that are yet to be processed. We utilize a stack data structure to maintain the hierarchy of nodes as they are constructed.
Steps:
This C++ solution employs an iterative approach using a stack. By iterating through the preorder list, it constructs the tree and manages left and right children using the stack. This method avoids recursion and utilizes an index map for inorder positions.
C++
JavaScript
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the stack and additional data structures like the map for indices.
The first node preorder[0] in the pre-order sequence is the root node. We find the position k of the root node in the in-order sequence, which can divide the in-order sequence into the left subtree inorder[0..k] and the right subtree inorder[k+1..].
Through the intervals of the left and right subtrees, we can calculate the number of nodes in the left and right subtrees, assumed to be a and b. Then in the pre-order nodes, the a nodes after the root node are the left subtree, and the b nodes after that are the right subtree.
Therefore, we design a function dfs(i, j, n), where i and j represent the starting positions of the pre-order sequence and the in-order sequence, respectively, and n represents the number of nodes. The return value of the function is the binary tree constructed with preorder[i..i+n-1] as the pre-order sequence and inorder[j..j+n-1] as the in-order sequence.
The execution process of the function dfs(i, j, n) is as follows:
n leq 0, it means there are no nodes, return a null node.v = preorder[i] of the pre-order sequence as the root node, and then use the hash table d to find the position k of the root node in the in-order sequence. Then the number of nodes in the left subtree is k - j, and the number of nodes in the right subtree is n - k + j - 1.l = dfs(i + 1, j, k - j) and the right subtree r = dfs(i + 1 + k - j, k + 1, n - k + j - 1).v as the root node and l and r as the left and right subtrees, respectively.The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes in the tree, because each node is processed once. |
| Iterative Approach | Time Complexity: O(n), where n is the number of nodes, as each node is visited once. |
| Hash Table + Recursion | — |
| 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. |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 394,414 views views
Watch 9 more video solutions →Practice Construct Binary Tree from Preorder and Inorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor