Phase 1: Given two arrays, identify the root and find it in inorder.

I give you two arrays — the preorder traversal and the inorder traversal of a binary tree. Reconstruct the tree.

Preorder visits root-left-right. Inorder visits left-root-right. Two different visit orders of the same tree. But how do you use them to reconstruct the original structure?

FIG. 1 — THE TWO TRAVERSALS AND THE TREE THEY ENCODE
Preorder
0
1
2
3
4
Inorder
9
0
3
1
15
2
20
3
7
4
Goal3920157
— Input arrays on the left, target tree on the right —

Given just two flat arrays and a tree to reconstruct, the challenge is figuring out which elements belong where. The partition arithmetic that couples the two arrays is off-by-one-prone, and even deciding how many nodes go left vs right is trickier than it looks.

FIG. 2 — FIND THE ROOT

Start with the preorder. In preorder traversal the root is always visited first. Tap the root in the preorder array.