Construction & Serialization

From Pre + In Order

Pre-order's first element is the root. Find it in the in-order array — everything to its left is the left subtree, everything to its right is the right subtree. Recurse on both halves. This uniquely reconstructs the tree.

O(n)

How It Works

Rebuilding a tree from its pre-order and in-order traversals hinges on what each order reveals. Pre-order's first element is always the current root. Locating that value in the in-order array splits it into the left subtree's values (everything before it) and the right subtree's values (everything after). Those sizes also tell you how to slice the remaining pre-order array, so both subtrees can be built recursively from their matching slices.

Searching in-order linearly at every step costs O(n^2) in the worst case; hashing each value to its in-order index up front makes every root lookup O(1), and tracking array boundaries with indices instead of copying slices brings the whole construction to O(n) time and O(n) space for the map plus O(h) recursion. This works cleanly because the problem guarantees unique values; duplicates would make the in-order split ambiguous.

Step-by-Step Visualization

Pre=[3,9,20,15,7], In=[9,3,15,20,7]

Root3 (first in preorder)

1/3

Code

Java

static TreeNode buildTree(int[] preorder, int[] inorder) {
  Map<Integer, Integer> map = new HashMap<>();
  for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
  int[] preIdx = {0};
  return build(preorder, map, preIdx, 0, inorder.length - 1);
}

static TreeNode build(int[] preorder, Map<Integer, Integer> map, int[] preIdx, int inStart, int inEnd) {
  if (inStart > inEnd) return null;
  int rootVal = preorder[preIdx[0]++];
  TreeNode node = new TreeNode(rootVal);
  int inIdx = map.get(rootVal);
  node.left = build(preorder, map, preIdx, inStart, inIdx - 1);
  node.right = build(preorder, map, preIdx, inIdx + 1, inEnd);
  return node;
}

Tips & Gotchas

1Pre-order first element = root

2Find root in in-order to determine left/right subtree sizes

3Use a hash map for O(1) root lookup in in-order array

Practice Problems

1Construct Binary Tree from Preorder and Inorder Traversal
2Construct Binary Tree from Inorder and Postorder Traversal
3Construct Binary Search Tree from Preorder Traversal
4Convert Sorted Array to Binary Search Tree

About the Construction & Serialization Pattern

Build a tree from its traversal orders, or convert a tree to/from a string representation. These test your understanding of how traversal orders uniquely define a tree's structure.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why can't a tree be reconstructed from pre-order and post-order alone?

Without in-order, you cannot always tell whether a lone child hangs left or right — a node with a single child produces identical pre/post sequences either way. In-order resolves the ambiguity because it places left-subtree values strictly before the root and right-subtree values strictly after. Pre+post only suffices for full binary trees.

What optimization takes this from O(n^2) to O(n)?

Two things: precompute a hash map from value to in-order index so finding each root's split point is O(1), and pass index boundaries into recursive calls instead of copying subarrays. Each node is then created with constant extra work.