Tree Construction

Rebuild binary trees from traversal sequences using recursive divide-and-conquer — a pattern that maps positional indices to subtrees.

10 min readLeetCode Patterns for InterviewsCode

The Pattern

Given two traversal sequences of a binary tree, you can uniquely reconstruct it — provided the traversals are consistent. The key observation: the first element of a preorder (or last of a postorder) is always the root. Find that root in the inorder array; everything left of it is the left subtree, everything right is the right subtree. Recurse.

Tree built from preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

For preorder + inorder: preorder[0] = 3 is the root. Find 3 in inorder at index 1. Left subtree has inorder[0:1] = [9] and preorder[1:2] = [9]. Right subtree has inorder[2:] = [15,20,7] and preorder[2:] = [20,15,7]. Recurse on each pair.

For inorder + postorder: postorder[-1] is the root. Same divide, but the left preorder section is taken from the left portion of the postorder array by length.

For preorder + postorder: the tree is not uniquely determined for full generality, but it works for full binary trees. Preorder[0] = root, preorder[1] = left child root. Find it in postorder to determine the split.

Template Code

Gobuild-tree-from-preorder-+-inorder-—-recursive.go

27 linesLn 1, Col 1Go

Preorder gives the root outright. Inorder tells you what goes left vs right. The recursive call receives slices that correspond to the same subtree in both arrays.

Gobuild-tree-from-inorder-+-postorder.go

20 linesLn 1, Col 1Go

Identical logic, just the root moves from preorder[0] to postorder[-1]. The slice arithmetic for the right subtree adjusts by excluding the last element.

Key Insight

The hash map optimization

Finding the root index in inorder is O(n) per call → O(n²) worst case. Pre-process inorder into a map (value → index) for O(1) lookup. Then the recursive solution runs in O(n) total.

When to Use

Restore serialized tree: LeetCode serializes trees as level-order arrays; but interviewers sometimes give traversal pairs.
Divide by root: Any problem where finding a root and splitting into left/right applies — not just construction, but also validation.
Full binary trees: Preorder + postorder uniquely determines the tree only when every node has 0 or 2 children (full binary tree).
MST-like problems: Tree reconstruction from traversal pairs shows up in compiler design (parse trees) and file system serialization.

Problems

#105Construct Binary Tree from Preorder and Inorder TraversalMediumDivide-and-conquer with hash map · O(n) time · O(n) space #106Construct Binary Tree from Inorder and Postorder TraversalMediumDivide-and-conquer from postorder root · O(n) time · O(n) space #889Construct Binary Tree from Preorder and Postorder TraversalMediumFull binary tree assumption · O(n) time · O(n) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Linked Lists & Trees