LeetCode · #105

Construct Binary Tree from Preorder and Inorder Solution

Given preorder and inorder traversals of a tree with unique values, construct and return the binary tree.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #105

🏗️

Pattern

Construction — preorder root + inorder split

Given two integer arrays preorder and inorder where preorder is the preorder traversal and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example

 Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: 3
        / \
       9   20
          /  \
         15   7

Constraints

 • 1 ≤ preorder.length ≤ 3000 • All values are unique • inorder.length == preorder.length 

Section Two · Approach 1

Linear Search for Root — O(n²)

For each recursive call, scan inorder to find the root's position. This linear search gives O(n) per level → O(n²) total. A HashMap pre-stores positions for O(1) lookup.

Section Three · Approach 2

Recursive + HashMap — O(n)

Key insight: the first element in preorder is always the root. Find that root's position in inorder — everything left is the left subtree, everything right is the right subtree. Recurse.

💡 Mental model: Preorder says "who's the boss" (root comes first). Inorder says "who sits left vs right of the boss." Together they uniquely define the tree. The HashMap lets you instantly find where the boss sits in the inorder line.

Algorithm

Step 1: Build a HashMap: inorder value → index.
Step 2: Maintain a preIdx pointer (starts at 0) that advances through preorder.
Step 3: Recursive build(inLeft, inRight):
Create node from preorder[preIdx++].
Find root's position in inorder: mid = map.get(node.val).
node.left = build(inLeft, mid - 1).
node.right = build(mid + 1, inRight).

🎯 Why preIdx advances globally:

Preorder visits root → left subtree → right subtree.
By incrementing a single pointer, we naturally consume the correct root for each successive recursive call.
The left subtree call consumes all its roots before the right subtree call begins.

Section Four · Trace

Visual Walkthrough

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

Section Five · Implementation

Code — Java & Python

Java — Recursive + HashMap

 import java.util.HashMap;
class Solution {
int preIdx = 0;
HashMap<Integer, Integer> inMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++)
            inMap.put(inorder[i], i);
return build(preorder, 0, inorder.length - 1);
    }
private TreeNode build(int[] preorder, int inLeft, int inRight) {
if (inLeft > inRight) return null;
TreeNode root = new TreeNode(preorder[preIdx++]);
int mid = inMap.get(root.val);

        root.left  = build(preorder, inLeft, mid - 1);
        root.right = build(preorder, mid + 1, inRight);
return root;
    }
}

Python — Recursive + dict

 class Solution:
def buildTree(self, preorder, inorder):
        in_map = {val: i for i, val in enumerate(inorder)}
        self.pre_idx = 0 def build(left, right):
if left > right: return None
val = preorder[self.pre_idx]
            self.pre_idx += 1
root = TreeNode(val)
            mid = in_map[val]
            root.left  = build(left, mid - 1)
            root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Linear search for root	O(n²)	O(h)
HashMap ← optimal	O(n)	O(n) — map + recursion

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single node	`[1], [1]`	Root only, no children.
Left-skewed	`[3,2,1], [1,2,3]`	Each node is only a left child.

⚠ Common Mistake: Building the right subtree before the left subtree. Preorder visits left subtree first — so the global preIdx must consume all left-subtree roots before the right subtree's roots. Always call build(left) before build(right).

← Back to Trees problems

LearningTree

LC 105 · Construct Binary Tree from Preorder and Inorder — Solution & Explanation | DSA Guide