105. Construct Binary Tree from Preorder and Inorder Traversal

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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