You’re in a coding interview. The interviewer says: “Given the preorder and inorder traversals of a binary tree, reconstruct the tree.” The first element of preorder is always the root. The root splits inorder into left and right subtrees. Apply that recursively and you have the tree. Construct Binary Tree from Preorder and Inorder Traversal is LeetCode #105, a tree reconstruction problem that tests your understanding of traversal properties.

This walkthrough covers the recursive algorithm, the hash map optimization that makes it O(n), and the index-tracking details that trip up candidates under pressure.

---

The Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal and inorder is the inorder traversal of the same binary tree, construct and return the binary tree. (LeetCode #105)

Example

Input preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output Tree with structure: root=3, left=9, right subtree rooted at 20 with children 15 (left) and 7 (right).

The preorder tells us 3 is the root. In the inorder array, 3 sits at index 1, so everything left of index 1 ([9]) is the left subtree and everything right ([15,20,7]) is the right subtree. Recurse on each half.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

This problem tests whether you understand what information preorder and inorder traversals encode, and whether you can translate that understanding into a clean recursive implementation.

Skill	What Interviewers Observe
Traversal properties	Do you know preorder gives root first, inorder splits left/right?
Recursion structure	Do you correctly compute left subtree size and advance the preorder index?
Index map optimization	Do you use a hash map for O(1) inorder lookups?
In-place index tracking	Do you avoid slicing arrays (which copies memory)?

---

Step 1: Clarifying Questions

1. Are all values unique? Yes. The problem guarantees unique values. Without uniqueness, the root’s position in inorder would be ambiguous.

2. Can either array be empty? If both are empty, return None. They’re always the same length.

3. Can I modify the input arrays? You shouldn’t need to. Use index bounds to track subarrays without slicing.

---

Step 2: A First (Non-Optimal) Idea

Find the root in inorder using a linear scan. This makes each recursive call O(n) for the lookup, leading to O(n^2) total for a skewed tree.

Approach	Time	Space
Linear scan for root	O(n^2) worst case	O(n)
Hash map for root lookup	O(n)	O(n)

The fix: preprocess inorder into a hash map {value: index} once, giving O(1) lookups.

---

Step 3: The Key Insight

The first element of preorder is always the root. Find that root in inorder. Everything to its left is the left subtree, everything to its right is the right subtree. Recurse with the matching subarrays (tracked by indices, not slices) to build left and right subtrees.

The preorder pointer advances in a specific order: root, then the entire left subtree, then the entire right subtree. Since we always build the left subtree first in the recursion, incrementing a single global pointer through preorder naturally produces the correct root for each subproblem.

---

Step 4: Optimal Strategy

1. Build a hash map from inorder values to their indices.
2. Maintain a pointer pre_idx into preorder, starting at 0.
3. Define a recursive function build(in_left, in_right):
   • If in_left > in_right, return None (empty subtree).
   • The current root is preorder[pre_idx]. Increment pre_idx.
   • Find the root’s position mid in inorder using the hash map.
   • Recursively build the left subtree: build(in_left, mid - 1).
   • Recursively build the right subtree: build(mid + 1, in_right).
4. Call build(0, len(inorder) - 1).

Order matters: build left before right, because preorder visits left subtree nodes before right subtree nodes.

---

Python Implementation

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    inorder_index = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = [0]  # mutable reference to track position in preorder

    def build(in_left: int, in_right: int) -> Optional[TreeNode]:
        if in_left > in_right:
            return None

        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)

        mid = inorder_index[root_val]
        root.left = build(in_left, mid - 1)
        root.right = build(mid + 1, in_right)
        return root

    return build(0, len(inorder) - 1)

Why this is interview-friendly:

• Hash map eliminates O(n) scan. The inorder_index dict gives O(1) root lookups.
• Mutable pre_idx avoids passing/returning indices. Using [0] (a list) allows the nested function to modify it. An alternative is nonlocal in Python 3.
• No array slicing. Slicing creates copies per call, turning O(n) space into O(n^2). Index bounds in_left and in_right keep it at O(n).

---

Time & Space Complexity

	Time	Space
Construct Binary Tree	O(n)	O(n)

Hash map gives O(1) lookup. Each node is created exactly once. Recursion depth is O(h): O(log n) for balanced trees, O(n) for skewed trees. The hash map uses O(n) space.

---

Common Interview Mistakes

1. Slicing preorder and inorder arrays. preorder[1:mid+1] creates a new copy per call, turning O(n) space into O(n^2) total. Use index bounds instead.

2. Searching linearly for the root in inorder. O(n) per call leads to O(n^2) total for skewed trees. The hash map makes it O(1).

3. Wrong subtree size. The left subtree has mid - in_left nodes. Use this count to correctly determine the preorder range if passing explicit bounds.

4. Building right before left. Preorder visits left subtree before right subtree. If you build the right subtree first, pre_idx will point to the wrong node. Order matters.

5. Mutating preorder directly. Using preorder.pop(0) is O(n) per pop (shifting all elements). Use a pointer instead.

---

What a Strong Candidate Sounds Like

“Preorder gives root first; inorder splits left and right subtrees at the root’s position. I preprocess inorder into a hash map for O(1) root lookups. I maintain a pointer into preorder. The next unprocessed element is always the root of the current subproblem. Left subtree build uses inorder indices to the left of the root; right subtree uses those to the right. O(n) time and space.”

---

Example Interview Dialogue

Interviewer: Walk through preorder = [3,9,20,15,7], inorder = [9,3,15,20,7].

Candidate: preorder[0] = 3 is the root. In inorder, 3 is at index 1. Left subtree: inorder [9] (indices 0 to 0). Right subtree: inorder [15,20,7] (indices 2 to 4). Recurse left: preorder[1] = 9, inorder range [0,0], no children. Recurse right: preorder[2] = 20, inorder index 3. Left of 20: [15], right of 20: [7]. Each is a leaf. Done.

Interviewer: What about the postorder + inorder variant?

Candidate: Same algorithm, but the root is the last element of postorder instead of the first. You advance a pointer from right to left through postorder, and build right subtree before left (since postorder visits right subtree before root from the end).

---

Related Problems

• Construct Binary Tree from Inorder and Postorder (LeetCode #106). Same idea: postorder gives root last.
• Serialize and Deserialize Binary Tree (LeetCode #297). Related tree encoding/decoding.
• Validate Binary Search Tree (LeetCode #98). Inorder traversal for validation, closely related traversal property.

---

Practice This in a Mock Interview

This is one of the cleanest tree reconstruction problems. The algorithm is elegant once you understand it, but the index tracking (which subtree range maps to which preorder elements) is where most bugs appear under pressure. Tracing through a small example by hand before coding is essential.

Start a mock interview for Construct Binary Tree on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code