Construct Binary Tree from Preorder and Inorder — LeetCode 105

LeetCode #105, Construct Binary Tree from Preorder and Inorder Traversal, is one of the most elegant tree problems you will encounter in coding interviews. The core idea is deceptively simple — given two arrays that represent different traversal orders of the same binary tree, you can uniquely reconstruct the original tree structure.

This problem appears frequently at Google, Amazon, and Meta because it tests whether you truly understand how traversal orders encode tree structure. You cannot solve it by memorizing a template — you have to understand why preorder and inorder together are sufficient to determine every node's position in the tree.

In this walkthrough, we will break down the key insight that makes this construct binary tree preorder inorder leetcode problem solvable, walk through the recursive algorithm step by step, and cover the hash map optimization that brings the solution from O(n squared) to O(n).

You are given two integer arrays: preorder and inorder. The preorder array contains the nodes of a binary tree in root-left-right order. The inorder array contains the same nodes in left-root-right order. Your task is to construct and return the original binary tree.

For example, given preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7], the output is a tree with root 3, left child 9, right child 20, and 20's children being 15 (left) and 7 (right). The problem guarantees that all values are unique and the arrays are valid representations of the same tree.

The reason this works at all is a fundamental property of binary trees: preorder traversal always visits the root first, while inorder traversal places the root between its left and right subtrees. Together, these two pieces of information let you split the problem into smaller subproblems recursively.

The entire leetcode 105 solution hinges on one insight: the first element of the preorder array is always the root of the current tree or subtree. Once you know the root, you find its position in the inorder array. Everything to the left of the root in inorder belongs to the left subtree, and everything to the right belongs to the right subtree.

This is the fundamental relationship between preorder and inorder that makes reconstruction possible. Preorder tells you which node is the root. Inorder tells you which nodes belong to the left subtree and which belong to the right. With these two pieces of information, you can recurse on the left and right halves independently.

Consider preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]. The root is 3 (first in preorder). In inorder, 3 is at index 1. That means the left subtree has 1 node (index 0 through 0, which is just [9]) and the right subtree has 3 nodes (index 2 through 4, which is [15, 20, 7]). You then recurse on each subtree using the corresponding slices of both arrays.

The recursive algorithm to reconstruct binary tree from preorder and inorder works as follows. First, build a hash map from the inorder array that maps each value to its index. This gives you O(1) lookup when you need to find where the root sits in the inorder array. Then, maintain a pointer into the preorder array that advances each time you create a new node.

The recursive function takes the left and right bounds of the current inorder subarray. If left is greater than right, the subtree is empty — return null. Otherwise, take the next value from preorder (advancing the pointer), create a new tree node, find its index in inorder using the hash map, and recurse. Build the left subtree first (with inorder bounds from left to rootIndex minus 1), then the right subtree (from rootIndex plus 1 to right).

The order matters — you must build the left subtree before the right subtree because preorder visits nodes in root-left-right order. As you consume values from the preorder array from left to right, the left subtree's nodes come before the right subtree's nodes. This is why the preorder pointer simply increments and everything works out correctly.

The total time complexity is O(n) because each node is visited exactly once, and the hash map gives O(1) index lookups. Space complexity is O(n) for the hash map plus O(h) for the recursion stack, where h is the tree height.

Let us trace through preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7] step by step. First, build the hash map: {9:0, 3:1, 15:2, 20:3, 7:4}. Initialize the preorder pointer at index 0.

Step 1: Take preorder[0] = 3. Create node 3. Find 3 in inorder at index 1. Left subtree uses inorder[0..0], right subtree uses inorder[2..4]. Step 2: Recurse left. Take preorder[1] = 9. Create node 9. Find 9 in inorder at index 0. Left subtree uses inorder[0..-1] which is empty. Right subtree uses inorder[1..0] which is also empty. Node 9 is a leaf.

Step 3: Back to the right subtree of node 3. Take preorder[2] = 20. Create node 20. Find 20 in inorder at index 3. Left subtree uses inorder[2..2], right subtree uses inorder[4..4]. Step 4: Recurse left. Take preorder[3] = 15. Node 15 is a leaf. Step 5: Recurse right. Take preorder[4] = 7. Node 7 is a leaf.

The final tree is: root 3 with left child 9, right child 20, and 20 has left child 15 and right child 7. Every node was created exactly once, the preorder pointer advanced exactly 5 times, and the hash map eliminated all linear scans. This is tree construction explained in its clearest form.

The simplest edge case is a single-node tree: preorder = [1], inorder = [1]. The root is 1, both subtrees are empty, and you return a single node. Your base case handles this naturally — after creating the root, both recursive calls hit left > right and return null.

A left-skewed tree (all nodes have only left children) like preorder = [3, 2, 1] and inorder = [1, 2, 3] is worth tracing. The root is 3, and in inorder 3 is at the far right, so the entire array except the last element belongs to the left subtree. The right subtree is always empty. This is the worst case for recursion depth — the stack goes O(n) deep.

A right-skewed tree is the mirror image: preorder = [1, 2, 3] and inorder = [1, 2, 3]. Here the root is always at the far left of the inorder subarray, so the left subtree is always empty. Both skewed cases work correctly without any special handling — the general algorithm covers them.

One subtle boundary to watch: the problem states values are unique, which is critical for correctness. If values could repeat, finding the root in inorder would be ambiguous — you might pick the wrong position and produce an incorrect tree. Always confirm this constraint in an interview before coding.

LeetCode 105 teaches you the deep relationship between tree traversal orders. Preorder gives you the root of every subtree. Inorder tells you the boundary between left and right. Together, they uniquely determine the tree. This insight extends to other reconstruction problems — you can also build a tree from inorder and postorder (LeetCode #106), where the last element of postorder is the root instead of the first.

The hash map optimization pattern appears across many tree and array problems. Whenever you need to repeatedly find an element's position in an array, precompute a value-to-index map. This is the same technique that powers the classic Two Sum solution, and recognizing it here shows strong pattern transfer.

If you are preparing for coding interviews, practice this problem until the recursive structure feels natural. Use YeetCode flashcards to drill the preorder-inorder relationship and the tree from two traversals reconstruction pattern. When you can explain why building the left subtree before the right subtree is essential — and what would break if you swapped the order — you have truly mastered this problem.