105. Construct Binary Tree from Preorder and Inorder Traversal

Quick Identifier

• Topic: trees
• Pattern: Tree DFS (divide by root)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: High
• LeetCode: 105

Quick Sights

• Time Complexity: preorder from the optimal approach.
• Space Complexity: inorder from the optimal approach.
• Core Mechanism: Given two integer arrays preorder and inorder of the same length (no duplicates), where inorder is an inorder traversal and preorder is a preorder traversal of the same binary tree, reconstruct the tree and return its root.

Concept Explanation

Given two integer arrays preorder and inorder of the same length (no duplicates), where inorder is an inorder traversal and preorder is a preorder traversal of the same binary tree, reconstruct the tree and return its root.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Preorder + inorder uniquely define the tree (with unique keys)
• Preorder’s first element is the subtree root; find it in inorder to split left/right blocks
• Classic divide-and-conquer on index ranges

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — find root in inorder with linear scan each step — O(n²).
• Better — hash inorder value → index for O(1) lookup — O(n) time / O(n) space.
• Optimal — same as better; one shared preorder index moving forward, boundaries on inorder — O(n) time / O(n) map + O(h) stack.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	indexByValue := make(map[int]int, len(inorder))
	for index, value := range inorder {
		indexByValue[value] = index
	}
	preorderIndex := 0
	var build func(int, int) *TreeNode
	build = func(inorderLeft int, inorderRight int) *TreeNode {
		if inorderLeft > inorderRight {
			return nil
		}
		rootValue := preorder[preorderIndex]
		preorderIndex++
		inorderRootIndex := indexByValue[rootValue]
		root := &TreeNode{Val: rootValue}
		root.Left = build(inorderLeft, inorderRootIndex-1)
		root.Right = build(inorderRootIndex+1, inorderRight)
		return root
	}
	return build(0, len(inorder)-1)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function buildTree(preorder, inorder) {
	const indexByValue = new Map();
	for (let index = 0; index < inorder.length; index++) {
		indexByValue.set(inorder[index], index);
	}
	let preorderIndex = 0;
	function build(inorderLeft, inorderRight) {
		if (inorderLeft > inorderRight) {
			return null;
		}
		const rootValue = preorder[preorderIndex];
		preorderIndex++;
		const inorderRootIndex = indexByValue.get(rootValue);
		const root = new TreeNode(rootValue);
		root.left = build(inorderLeft, inorderRootIndex - 1);
		root.right = build(inorderRootIndex + 1, inorderRight);
		return root;
	}
	return build(0, inorder.length - 1);
}

Walkthrough

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

Invariant: each recursive call owns a contiguous segment of inorder; preorder advances exactly once per created node.

Edge Cases

• Single node arrays
• Completely skewed tree — recursion depth O(n)

Pitfalls

• Advancing preorder index before building subtrees (must consume root first then left then right to match preorder layout)
• Duplicate values — problem forbids; otherwise indexing breaks

Similar Problems

• 100. Same Tree — validate reconstructions by traversal equality checks.
• 098. Validate Binary Search Tree — reinforces ordering reasoning on trees built elsewhere.
• 226. Invert Binary Tree — structural transforms after you can already build trees.

Variants

• Postorder + inorder split — root comes from end of postorder instead of front of preorder.
• Serialize / deserialize without duplicates assumption — need sentinels or counts.

Mind-Map Tags

#trees #dfs #preorder #inorder #divide-conquer #hash-index