Build Binary Tree From Two Traversals

Why two traversals needed

Preorder alone is ambiguous. Inorder gives left/right structure. Together they fix the tree.

Preorder + Inorder

int preIdx = 0;
Node build(int[] preorder, int[] inorder, int l, int r, Map inMap) {
  if (l > r) return null;
  int val = preorder[preIdx++];
  Node node = new Node(val);
  int idx = inMap.get(val);
  node.left = build(preorder, inorder, l, idx - 1, inMap);
  node.right = build(preorder, inorder, idx + 1, r, inMap);
  return node;
}

Postorder + Inorder

Process postorder in reverse. Root at end. Recursion mirror-image of preorder.

Preorder + Postorder

Ambiguous for general binary trees. Works if it's full binary tree (every internal node has 2 children).