LeetCode 105 · Medium · Trees

Construct Binary Tree from Preorder and Inorder Traversal

You get the preorder and the inorder traversal of a binary tree with distinct values. Rebuild the tree and return its root.

O(n²)time · O(n) with a hash map
O(n²)space · slices · O(n) with indices
divide and conquerpreorder picks, inorder splits

1 to 15 distinct values, −99 to 99 · both lists hold the same values · the tree may be at most 4 levels deep

preorder root first, then the whole left subtree, then the right

root

inorder left subtree, root, right subtree · blue = goes left · green = goes right

mid

Call stack one frame per buildTree call · the root it is building · newest on the right

public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0 || inorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); int mid = 0; while (inorder[mid] != preorder[0]) { mid++; } root.left = buildTree( Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid)); root.right = buildTree( Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length)); return root;}
preorder
—
inorder
—
root
—
mid
—
nodes built
0

Why it works

  1. Brute force has nothing to try: enumerating tree shapes and checking both traversals is exponential. The two orders together pin the tree down uniquely when values are distinct.
  2. Preorder says who the root is; inorder says who goes where. The first preorder value is the root. Everything left of it in inorder is the left subtree, everything right of it the right subtree. The left subtree has mid nodes, so it also takes the next mid preorder values. Recurse on both halves.
  3. Cost: each of the n calls scans for mid and copies slices with Arrays.copyOfRange, O(n) per call: O(n²) in the worst case (a chain). On a chain the slices still waiting on the stack also hold O(n²) values. A HashMap from value to inorder index plus index bounds instead of copyOfRange slices makes both O(n).
  4. Pitfall: splitting preorder by value instead of by count. The left subtree's preorder block is exactly the mid values after the root; the code never looks for a boundary value in preorder.
  5. Related: postorder + inorder (106) works the same way with the root at the end. Preorder + postorder alone cannot always tell a lone left child from a lone right child.