Build a Tree from Traversals

One traversal alone can't pin down a binary tree, because different shapes give the same list. Two traversals usually can. Preorder or postorder tells you which value is the root, and inorder tells you which values sit to its left and right. Recursing on the two halves rebuilds the whole tree.

The idea#

Preorder lists the root first, and postorder lists it last. In inorder, everything left of the root's position belongs to the left subtree, and everything right of it belongs to the right subtree. That one split gives you the sizes of both subtrees, and the same rule applies inside each.

Call the preorder or postorder array the root list, since that is where you read each root from. The order in which you read it decides the order in which you build the subtrees. Preorder read forward gives root, left, right, so you build left first. Any other reading order changes which subtree comes next.

That is the whole algorithm; the catch is speed. The textbook version slices the arrays and calls inorder.index(root) at every step. Each slice and each search is $O(n)$ , so the build is $O(n^2)$ on a skewed tree. The fix: store every value's inorder position in a hashmap once, and walk the root list with a single moving pointer instead of slicing. That makes it $O(n)$ .

How to spot it#

The input is two traversal arrays, and the output is a tree.

"Construct the binary tree from its preorder and inorder (or postorder) traversal."
Values are distinct. That is what makes the inorder index lookup unambiguous.
Rebuilding a BST from its preorder alone is the same idea, with value bounds in place of the inorder split.

Template#

Here is the fast version from "The idea": a position map for the splits and one moving pointer into preorder. Nodes follow LeetCode's TreeNode(val, left, right).

pos = map from each value to its inorder index   # O(1) splits
nxt = 0                                          # next unused root value
build(lo, hi):                     # this subtree covers inorder[lo..hi]
    if lo > hi: return None
    root = new node with preorder[nxt]; nxt += 1
    mid = pos[root.val]
    root.left = build(lo, mid - 1)   # preorder lists the left side first
    root.right = build(mid + 1, hi)
    return root
return build(0, n - 1)

Pitfalls#

These mistakes cost time or build the wrong tree.

index() plus slicing. It reads well, but it is $O(n^2)$ . Use a position map and index ranges.
Wrong build order. The build order must match the order in which you read the root list.
Pointers stored on the object. Keeping pre_index and post_index in __init__ breaks when the same Solution instance builds a second tree. Keep them local to the call.
Duplicate values. The inorder split assumes every value appears once.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Construct Binary Tree from Preorder and Inorder Traversal

This is the template. The next preorder value is the root, and its inorder index splits the range. Build left, then right.

Hint: Construct Binary Tree from Inorder and Postorder Traversal

Read postorder from the end, so the next value is the root. Reading postorder backward gives root, right, left. So build the right subtree before the left.

Hint: Construct Binary Tree from Preorder and Postorder Traversal

Without inorder there is no split index. Use two pointers, pre and post. Preorder adds a parent before its children; postorder adds a node only after its whole subtree. After you create a node from preorder, keep building children while postorder[post] is not that node's value. When it matches, the subtree is complete: move post on by one.

Hint: Preorder and postorder: one child

When a node has only one child, preorder plus postorder can't tell a left child from a right one. LeetCode accepts any valid tree, so make it the left child.

Hint: Convert Sorted Array to Binary Search Tree

The middle element becomes the root, so both sides have the same size. Build the left subtree from the left half and the right subtree from the right half.

Key takeaways#

Preorder's first value (or postorder's last) is the root; inorder splits left from right.
Build with index ranges and a position map for $O(n)$ , not slices and index().
Inorder + postorder: read from the end and build right before left.
Preorder + postorder: two pointers; a subtree ends when postorder reaches its root.

Core idea#

One traversal cannot pin down a binary tree, but two usually can. Preorder or postorder gives the root. Inorder splits the remaining values into left and right subtrees.

Key points#

Preorder lists the root first. Postorder lists it last.
In inorder, values left of the root belong to the left subtree. Values right of it belong to the right subtree.
Slicing plus inorder.index(root) is $O(n^2)$ on a skewed tree.
Store each inorder position in a map once, and walk preorder with one pointer. That is $O(n)$ .
Values must be distinct for the inorder lookup.
A BST from preorder alone uses value bounds instead of the inorder split.

Pairs#

Pair	Root from	Build order
Preorder + inorder	next preorder value	left, then right
Inorder + postorder	next value from the end of postorder	right, then left
Preorder + postorder	next preorder value; subtree ends when postorder reaches it	left, then right

Template#

pos = map from each value to its inorder index
nxt = 0                              # next unused preorder value
build(lo, hi):                       # covers inorder[lo..hi]
    if lo > hi: return None
    root = new node with preorder[nxt]; nxt += 1
    mid = pos[root.val]
    root.left = build(lo, mid - 1)
    root.right = build(mid + 1, hi)
    return root
return build(0, n - 1)

Pitfalls#

index() plus slicing hides $O(n^2)$ .
Building left first when you read postorder from the end.
Pointers stored on the Solution object. They break on a second build. Keep them local.
Pre + post cannot tell a single left child from a single right child. Any valid tree is accepted.

Say it in an interview#

"Preorder gives the root, inorder gives the split."
"A position map and index ranges make it O(n) instead of O(n²)."