Skip to main content
Talentd

Construct Binary Tree from Preorder and Inorder Traversal - Solution & Explanation

MediumArrayHash TableDivide and ConquerTree24 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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 <= 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.

Approach Overview

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 1: Recursive Approach

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:

  1. Start with the entire range of the inorder traversal.
  2. The first element of the preorder list is the root; locate it in the inorder list.
  3. Divide the inorder list into left and right subtrees based on this root.
  4. Recursively build the left and right subtrees using the remaining elements of the preorder list.
  5. Use an index map to quickly locate the root in the inorder list, improving the performance to O(n).

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Approach

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:

  1. Initialize a stack with the root node derived from the first element of the preorder list.
  2. Iterate over the preorder traversal and use the stack to construct tree nodes.
  3. Maintain a pointer to track the current position in the inorder sequence, pushing new nodes onto the stack for left children and popping from the stack for right children.

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table + Recursion

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:

  • If n leq 0, it means there are no nodes, return a null node.
  • Take out the first 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.
  • Recursively construct the left subtree l = dfs(i + 1, j, k - j) and the right subtree r = dfs(i + 1 + k - j, k + 1, n - k + j - 1).
  • Finally, return the binary tree with 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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach

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.

Iterative Approach

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.

Hash Table + Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Divide and Conquer with Hash MapO(n)O(n)Most common interview solution. Clear logic using preorder for roots and inorder for subtree boundaries.
Iterative Stack ConstructionO(n)O(n)Useful when avoiding recursion or demonstrating deeper understanding of traversal mechanics.

Video Solution

L34. Construct a Binary Tree from Preorder and Inorder Traversal | C++ | Java • take U forward • 455,238 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Construct Binary Tree from Preorder and Inorder Traversal easy or hard?
Construct Binary Tree from Preorder and Inorder Traversal is generally classified as a medium difficulty problem. The challenge lies in understanding how preorder identifies the root while inorder determines subtree partitions. Once that relationship is clear, the divide-and-conquer implementation becomes straightforward.
Construct Binary Tree from Preorder and Inorder Traversal Python/Java solution
Python and Java implementations typically follow the recursive approach. Build a hash map from inorder values to indices, then recursively construct nodes using the preorder pointer and inorder boundaries. Both implementations run in O(n) time and O(n) space.
How to solve Construct Binary Tree from Preorder and Inorder Traversal in O(n)?
Store the index of every value from the inorder array in a hash map. Use a pointer that moves through the preorder array to create nodes in root-first order. For each node, split the inorder range into left and right parts and recursively build the subtrees. Because each node and lookup occurs once, the algorithm runs in O(n) time.
What is the best approach for Construct Binary Tree from Preorder and Inorder Traversal?
The best approach uses recursive divide and conquer with a hash map for quick index lookup in the inorder array. Preorder identifies the root node, while inorder determines the left and right subtree boundaries. Using a hash map avoids repeated searches and keeps the total time complexity at O(n). This is the standard interview solution.
Is Construct Binary Tree from Preorder and Inorder Traversal asked at Google/Amazon/Meta?
Construct Binary Tree from Preorder and Inorder Traversal is a common medium-level tree problem asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of tree traversals, recursion, and divide-and-conquer techniques. Variations of this reconstruction problem appear frequently in technical interviews.
What data structure is used in Construct Binary Tree from Preorder and Inorder Traversal?
The solution uses a binary tree structure along with a hash map to store inorder indices for quick lookup. Recursion or a stack manages the construction process. These structures allow efficient subtree splitting and ensure the algorithm runs in linear time.
What is the time complexity of Construct Binary Tree from Preorder and Inorder Traversal?
The optimal solution runs in O(n) time because each node is processed exactly once. A hash map allows O(1) lookup of each value's index in the inorder traversal. Space complexity is O(n) due to the recursion stack and the hash map storing inorder indices.

Ready to solve this problem?

Practice Construct Binary Tree from Preorder and Inorder Traversal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Construct Binary Tree from Inorder and Postorder Traversal