105. Construct Binary Tree from Preorder and Inorder Traversal
Problem Description
You are given two integer arrays representing different traversals of the same binary tree:
preorder
: the preorder traversal (root → left → right)inorder
: the inorder traversal (left → root → right)
Your task is to reconstruct and return the original binary tree from these two traversals.
The problem leverages the properties of tree traversals:
- In preorder traversal, the first element is always the root node
- In inorder traversal, elements to the left of the root are in the left subtree, and elements to the right are in the right subtree
The solution uses a recursive approach with a hash table for efficient lookups. The key insight is that once we identify the root from preorder[0]
, we can find its position in the inorder array to determine which elements belong to the left and right subtrees.
The recursive function dfs(i, j, n)
builds the tree where:
i
is the starting index in the preorder arrayj
is the starting index in the inorder arrayn
is the number of nodes to process
For each recursive call:
- The root value is taken from
preorder[i]
- Its position
k
in the inorder array is found using the hash table - The left subtree has
k - j
nodes (elements before root in inorder) - The right subtree has
n - k + j - 1
nodes (elements after root in inorder) - Recursively build left and right subtrees with appropriate index ranges
- Return a TreeNode with the root value and constructed subtrees
The hash table d
maps each value to its index in the inorder array for O(1) lookups, making the overall time complexity O(n).
Intuition
The key observation is understanding what preorder and inorder traversals tell us about the tree structure.
In preorder traversal, we visit nodes in the order: root → left subtree → right subtree. This means the first element is always the root of the current tree or subtree.
In inorder traversal, we visit nodes in the order: left subtree → root → right subtree. This means all nodes to the left of the root value belong to the left subtree, and all nodes to the right belong to the right subtree.
By combining these two properties, we can reconstruct the tree recursively:
- Pick the first element from preorder - this is our root
- Find this root in inorder - this splits our nodes into left and right groups
- Count how many nodes are in the left subtree (elements before root in inorder)
- Use this count to determine which elements in preorder belong to left vs right subtrees
For example, if preorder = [3,9,20,15,7]
and inorder = [9,3,15,20,7]
:
- Root is
3
(first in preorder) - In inorder,
9
is left of3
, so it's in left subtree 15,20,7
are right of3
, so they're in right subtree- In preorder, after root
3
, the next 1 element (9
) forms the left subtree - The remaining elements (
20,15,7
) form the right subtree
The challenge is efficiently tracking which portions of the arrays correspond to which subtree. We use index arithmetic: if we know the starting positions and the number of nodes, we can calculate the exact array segments for each recursive call.
The hash table optimization comes from needing to repeatedly find where the root appears in inorder. Instead of searching each time (O(n)), we precompute all positions (O(1) lookup).
Solution Approach
The solution uses a hash table combined with recursion to efficiently reconstruct the binary tree.
Step 1: Build Hash Table
d = {v: i for i, v in enumerate(inorder)}
We create a dictionary d
that maps each node value to its index in the inorder array. This allows O(1) lookup time when finding the root's position.
Step 2: Define Recursive Function
The core function dfs(i, j, n)
takes three parameters:
i
: starting index in the preorder arrayj
: starting index in the inorder arrayn
: number of nodes to process in this subtree
Step 3: Base Case
if n <= 0: return None
If there are no nodes to process, return None
.
Step 4: Identify Root and Split Point
v = preorder[i] # Root value k = d[v] # Root's position in inorder
The root is always at preorder[i]
. We find its position k
in the inorder array using our hash table.
Step 5: Calculate Subtree Sizes
- Left subtree size:
k - j
(nodes before root in inorder segment) - Right subtree size:
n - k + j - 1
(nodes after root in inorder segment)
Step 6: Recursive Construction
l = dfs(i + 1, j, k - j) # Left subtree r = dfs(i + 1 + k - j, k + 1, n - k + j - 1) # Right subtree
For the left subtree:
- Preorder starts at
i + 1
(skip the root) - Inorder starts at
j
(same start) - Process
k - j
nodes
For the right subtree:
- Preorder starts at
i + 1 + k - j
(skip root and all left subtree nodes) - Inorder starts at
k + 1
(skip left subtree and root) - Process
n - k + j - 1
nodes
Step 7: Build and Return Node
return TreeNode(v, l, r)
Create a new TreeNode with value v
, left child l
, and right child r
.
The initial call dfs(0, 0, len(preorder))
starts with the entire arrays and recursively builds the complete tree from top to bottom.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through a small example with preorder = [3,9,20,15,7]
and inorder = [9,3,15,20,7]
.
Initial Setup:
- Build hash table:
d = {9:0, 3:1, 15:2, 20:3, 7:4}
- Call
dfs(0, 0, 5)
to process all 5 nodes
First Call: dfs(0, 0, 5)
- Root value:
preorder[0] = 3
- Find root position:
d[3] = 1
- Left subtree size:
1 - 0 = 1
node - Right subtree size:
5 - 1 + 0 - 1 = 3
nodes - Build left:
dfs(1, 0, 1)
- Build right:
dfs(2, 2, 3)
Left Subtree: dfs(1, 0, 1)
- Root value:
preorder[1] = 9
- Find root position:
d[9] = 0
- Left subtree size:
0 - 0 = 0
nodes → returnsNone
- Right subtree size:
1 - 0 + 0 - 1 = 0
nodes → returnsNone
- Returns:
TreeNode(9)
Right Subtree: dfs(2, 2, 3)
- Root value:
preorder[2] = 20
- Find root position:
d[20] = 3
- Left subtree size:
3 - 2 = 1
node - Right subtree size:
3 - 3 + 2 - 1 = 1
node - Build left:
dfs(3, 2, 1)
→ returnsTreeNode(15)
- Build right:
dfs(4, 4, 1)
→ returnsTreeNode(7)
- Returns:
TreeNode(20, TreeNode(15), TreeNode(7))
Final Tree Structure:
3 / \ 9 20 / \ 15 7
The algorithm correctly reconstructs the tree by using preorder to identify roots and inorder to determine subtree boundaries. Each recursive call processes a specific segment of both arrays, building the tree from top to bottom.
Solution Implementation
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7
8from typing import List, Optional
9
10class Solution:
11 def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
12 """
13 Construct a binary tree from preorder and inorder traversal arrays.
14
15 Args:
16 preorder: List of node values in preorder traversal
17 inorder: List of node values in inorder traversal
18
19 Returns:
20 Root node of the constructed binary tree
21 """
22
23 def build_subtree(preorder_start: int, inorder_start: int, subtree_size: int) -> Optional[TreeNode]:
24 """
25 Recursively build a subtree.
26
27 Args:
28 preorder_start: Starting index in preorder array for current subtree
29 inorder_start: Starting index in inorder array for current subtree
30 subtree_size: Number of nodes in current subtree
31
32 Returns:
33 Root node of the subtree
34 """
35 # Base case: empty subtree
36 if subtree_size <= 0:
37 return None
38
39 # The first element in preorder segment is always the root
40 root_value = preorder[preorder_start]
41
42 # Find root's position in inorder array
43 root_inorder_index = inorder_index_map[root_value]
44
45 # Calculate size of left subtree
46 left_subtree_size = root_inorder_index - inorder_start
47
48 # Recursively build left subtree
49 # Left subtree in preorder: starts right after root
50 # Left subtree in inorder: starts at inorder_start
51 left_child = build_subtree(
52 preorder_start + 1,
53 inorder_start,
54 left_subtree_size
55 )
56
57 # Recursively build right subtree
58 # Right subtree in preorder: starts after root and left subtree
59 # Right subtree in inorder: starts after root
60 right_child = build_subtree(
61 preorder_start + 1 + left_subtree_size,
62 root_inorder_index + 1,
63 subtree_size - left_subtree_size - 1
64 )
65
66 # Create and return the root node with its children
67 return TreeNode(root_value, left_child, right_child)
68
69 # Create a hashmap for O(1) lookup of indices in inorder array
70 inorder_index_map = {value: index for index, value in enumerate(inorder)}
71
72 # Build the entire tree starting from index 0 in both arrays
73 return build_subtree(0, 0, len(preorder))
74
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16class Solution {
17 private int[] preorderArray;
18 private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
19
20 /**
21 * Constructs a binary tree from preorder and inorder traversal arrays.
22 * @param preorder array representing preorder traversal of the tree
23 * @param inorder array representing inorder traversal of the tree
24 * @return root node of the constructed binary tree
25 */
26 public TreeNode buildTree(int[] preorder, int[] inorder) {
27 int totalNodes = preorder.length;
28 this.preorderArray = preorder;
29
30 // Build a map for quick lookup of each value's index in inorder array
31 for (int i = 0; i < totalNodes; ++i) {
32 inorderIndexMap.put(inorder[i], i);
33 }
34
35 // Start recursive construction from the entire array range
36 return dfs(0, 0, totalNodes);
37 }
38
39 /**
40 * Recursively constructs a subtree using depth-first search.
41 * @param preorderStartIndex starting index in preorder array for current subtree
42 * @param inorderStartIndex starting index in inorder array for current subtree
43 * @param subtreeSize number of nodes in current subtree
44 * @return root node of the constructed subtree
45 */
46 private TreeNode dfs(int preorderStartIndex, int inorderStartIndex, int subtreeSize) {
47 // Base case: empty subtree
48 if (subtreeSize <= 0) {
49 return null;
50 }
51
52 // The first element in preorder segment is always the root
53 int rootValue = preorderArray[preorderStartIndex];
54
55 // Find root's position in inorder array
56 int rootInorderIndex = inorderIndexMap.get(rootValue);
57
58 // Calculate size of left subtree
59 int leftSubtreeSize = rootInorderIndex - inorderStartIndex;
60
61 // Recursively build left subtree
62 // Left subtree's preorder starts right after current root
63 // Left subtree's inorder starts at same position
64 TreeNode leftChild = dfs(preorderStartIndex + 1, inorderStartIndex, leftSubtreeSize);
65
66 // Recursively build right subtree
67 // Right subtree's preorder starts after root and entire left subtree
68 // Right subtree's inorder starts right after root position
69 // Right subtree size = total size - 1 (root) - left subtree size
70 TreeNode rightChild = dfs(preorderStartIndex + 1 + leftSubtreeSize,
71 rootInorderIndex + 1,
72 subtreeSize - 1 - leftSubtreeSize);
73
74 // Create and return root node with constructed children
75 return new TreeNode(rootValue, leftChild, rightChild);
76 }
77}
78
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
15 int totalNodes = preorder.size();
16
17 // Create a map to store the index of each value in inorder array
18 // This allows O(1) lookup when finding the root position in inorder
19 unordered_map<int, int> inorderIndexMap;
20 for (int i = 0; i < totalNodes; ++i) {
21 inorderIndexMap[inorder[i]] = i;
22 }
23
24 // Recursive function to build the tree
25 // Parameters:
26 // - preorderStart: starting index in preorder array
27 // - inorderStart: starting index in inorder array
28 // - subtreeSize: number of nodes in current subtree
29 function<TreeNode*(int, int, int)> buildSubtree = [&](int preorderStart, int inorderStart, int subtreeSize) -> TreeNode* {
30 // Base case: empty subtree
31 if (subtreeSize <= 0) {
32 return nullptr;
33 }
34
35 // The first element in preorder range is always the root
36 int rootValue = preorder[preorderStart];
37
38 // Find root's position in inorder array
39 int rootIndexInInorder = inorderIndexMap[rootValue];
40
41 // Calculate size of left subtree
42 int leftSubtreeSize = rootIndexInInorder - inorderStart;
43
44 // Recursively build left subtree
45 // Left subtree in preorder: starts right after root
46 // Left subtree in inorder: from inorderStart to rootIndexInInorder-1
47 TreeNode* leftChild = buildSubtree(preorderStart + 1, inorderStart, leftSubtreeSize);
48
49 // Recursively build right subtree
50 // Right subtree in preorder: starts after root and left subtree
51 // Right subtree in inorder: starts right after root
52 // Right subtree size: total - 1(root) - leftSubtreeSize
53 TreeNode* rightChild = buildSubtree(preorderStart + 1 + leftSubtreeSize,
54 rootIndexInInorder + 1,
55 subtreeSize - 1 - leftSubtreeSize);
56
57 // Create and return the root node with its children
58 return new TreeNode(rootValue, leftChild, rightChild);
59 };
60
61 // Build the entire tree starting from index 0 with all nodes
62 return buildSubtree(0, 0, totalNodes);
63 }
64};
65
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15/**
16 * Constructs a binary tree from preorder and inorder traversal arrays
17 * @param preorder - Array containing preorder traversal of the tree
18 * @param inorder - Array containing inorder traversal of the tree
19 * @returns The root node of the constructed binary tree
20 */
21function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
22 // Create a map to store the index of each value in the inorder array for O(1) lookup
23 const inorderIndexMap: Map<number, number> = new Map();
24 const treeSize: number = inorder.length;
25
26 // Populate the map with value -> index pairs from inorder array
27 for (let i = 0; i < treeSize; i++) {
28 inorderIndexMap.set(inorder[i], i);
29 }
30
31 /**
32 * Recursively builds the tree using preorder and inorder information
33 * @param preorderIndex - Current index in the preorder array
34 * @param inorderStart - Start index of the current subtree in inorder array
35 * @param subtreeSize - Number of nodes in the current subtree
36 * @returns Root node of the current subtree
37 */
38 const buildSubtree = (preorderIndex: number, inorderStart: number, subtreeSize: number): TreeNode | null => {
39 // Base case: empty subtree
40 if (subtreeSize <= 0) {
41 return null;
42 }
43
44 // The current root value is at preorderIndex in preorder array
45 const rootValue: number = preorder[preorderIndex];
46
47 // Find the position of root in inorder array
48 const rootInorderIndex: number = inorderIndexMap.get(rootValue)!;
49
50 // Calculate the size of left subtree
51 const leftSubtreeSize: number = rootInorderIndex - inorderStart;
52
53 // Recursively build left subtree
54 // Left subtree starts at preorderIndex + 1 in preorder array
55 const leftChild: TreeNode | null = buildSubtree(
56 preorderIndex + 1,
57 inorderStart,
58 leftSubtreeSize
59 );
60
61 // Recursively build right subtree
62 // Right subtree starts after left subtree in preorder array
63 const rightChild: TreeNode | null = buildSubtree(
64 preorderIndex + 1 + leftSubtreeSize,
65 rootInorderIndex + 1,
66 subtreeSize - 1 - leftSubtreeSize
67 );
68
69 // Create and return the current node with its children
70 return new TreeNode(rootValue, leftChild, rightChild);
71 };
72
73 // Start building the tree from the root
74 return buildSubtree(0, 0, treeSize);
75}
76
Time and Space Complexity
Time Complexity: O(n)
The algorithm builds a binary tree from preorder and inorder traversals. The main operations are:
- Creating a hash map
d
from the inorder list takesO(n)
time - The recursive function
dfs
visits each node exactly once to construct the tree - At each node, we perform constant time operations: finding the value in the hash map (
O(1)
), creating a TreeNode (O(1)
), and making recursive calls - Since we process each of the
n
nodes exactly once withO(1)
work per node, the total time complexity isO(n)
Space Complexity: O(n)
The space usage comes from:
- The hash map
d
storing the inorder indices requiresO(n)
space - The recursion stack depth in the worst case (skewed tree) can be
O(n)
- The output tree itself contains
n
nodes, requiringO(n)
space - Therefore, the overall space complexity is
O(n)
Common Pitfalls
1. Index Calculation Errors for Right Subtree
One of the most common mistakes is incorrectly calculating the starting index or size for the right subtree, especially the preorder starting index.
Incorrect Implementation:
# Wrong: forgetting to account for left subtree size right_child = build_subtree( preorder_start + 1, # ❌ This would re-process left subtree nodes root_inorder_index + 1, subtree_size - left_subtree_size - 1 )
Correct Implementation:
# Correct: skip root AND all left subtree nodes right_child = build_subtree( preorder_start + 1 + left_subtree_size, # ✓ Skip root + left subtree root_inorder_index + 1, subtree_size - left_subtree_size - 1 )
2. Assuming No Duplicate Values
The solution relies on a hash map to find the root's position in the inorder array. If duplicate values exist, the hash map will only store the last occurrence's index, leading to incorrect tree construction.
Problem Example:
preorder = [1, 2, 1, 3] inorder = [1, 2, 1, 3] # Hash map would be {1: 2, 2: 1, 3: 3}, losing the first '1' at index 0
Solution: Instead of using a global hash map, pass the valid range and search within that range:
def build_subtree(pre_start, in_start, in_end):
if pre_start >= len(preorder) or in_start > in_end:
return None
root_val = preorder[pre_start]
# Search only within the valid inorder range
root_index = -1
for i in range(in_start, in_end + 1):
if inorder[i] == root_val:
root_index = i
break
# Continue with tree construction...
3. Off-by-One Errors in Size Calculations
Calculating the right subtree size incorrectly is another frequent mistake.
Incorrect:
# Wrong: forgetting to subtract 1 for the root right_subtree_size = subtree_size - left_subtree_size # ❌
Correct:
# Correct: total size - left subtree - root (1) right_subtree_size = subtree_size - left_subtree_size - 1 # ✓
4. Not Handling Edge Cases
Failing to handle empty arrays or single-node trees can cause runtime errors.
Add validation:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
# Handle edge cases
if not preorder or not inorder:
return None
if len(preorder) != len(inorder):
raise ValueError("Traversal arrays must have the same length")
# Continue with normal logic...
5. Mixing Up Array Boundaries
Using absolute indices instead of relative positions within the current subtree segment.
Incorrect Approach (using global indices):
def dfs(pre_left, pre_right, in_left, in_right):
if pre_left > pre_right:
return None
# Complex index management...
Better Approach (using start + size):
def dfs(pre_start, in_start, size):
if size <= 0:
return None
# Cleaner, less error-prone
The start + size approach used in the solution is generally cleaner and reduces the chance of boundary errors compared to maintaining four separate boundary indices.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https assets algo monster cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger problem using the solutions
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https assets algo monster binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Want a Structured Path to Master System Design Too? Don’t Miss This!