Facebook Pixel

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 array
  • j is the starting index in the inorder array
  • n is the number of nodes to process

For each recursive call:

  1. The root value is taken from preorder[i]
  2. Its position k in the inorder array is found using the hash table
  3. The left subtree has k - j nodes (elements before root in inorder)
  4. The right subtree has n - k + j - 1 nodes (elements after root in inorder)
  5. Recursively build left and right subtrees with appropriate index ranges
  6. 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).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Pick the first element from preorder - this is our root
  2. Find this root in inorder - this splits our nodes into left and right groups
  3. Count how many nodes are in the left subtree (elements before root in inorder)
  4. 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 of 3, so it's in left subtree
  • 15,20,7 are right of 3, 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 array
  • j: starting index in the inorder array
  • n: 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 Evaluator

Example 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 → returns None
  • Right subtree size: 1 - 0 + 0 - 1 = 0 nodes → returns None
  • 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) → returns TreeNode(15)
  • Build right: dfs(4, 4, 1) → returns TreeNode(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 takes O(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 with O(1) work per node, the total time complexity is O(n)

Space Complexity: O(n)

The space usage comes from:

  • The hash map d storing the inorder indices requires O(n) space
  • The recursion stack depth in the worst case (skewed tree) can be O(n)
  • The output tree itself contains n nodes, requiring O(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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More