Construct Binary Tree from Preorder and Inorder Traversal

A binary tree with distinct values was traversed twice:

• preorder lists the values in pre-order (node, then its left subtree, then its right subtree);
• inorder lists them in in-order (left subtree, then node, then right subtree).

Rebuild the original tree from these two lists and return its root. With distinct values the two traversals determine the tree uniquely.

The judge prints the tree you return as a level-order array, with null for missing children (trailing nulls are dropped).

Example 1

Example 2

Example 3

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= values <= 3000; all values are distinct
• Both lists come from the same valid binary tree.

Pattern Path · Trees: DFS · problem 88 of 169

Start simple

Recursively take the root from preorder, search for it linearly in inorder and slice both lists for the subtrees: O(n²) time on skewed trees because of the searches and copies.

The key idea

Two facts drive the reconstruction. In pre-order, a subtree’s root always comes first. In in-order, a root sits between its left subtree and its right subtree. So the first pre-order value is the root, and its position in the in-order list splits the remaining values into left and right parts.

That split also tells you sizes: if the root is at in-order index m and the current in-order range starts at lo, the left subtree has m - lo nodes. Those are exactly the next m - lo values in pre-order, followed by the right subtree’s values. Applying the same rule recursively to each part rebuilds the whole tree.

To keep it linear, avoid slicing and searching. Store a map from value to in-order index once, and walk through preorder with a single shared pointer: because pre-order visits node, left, right, building the left subtree fully before the right one consumes the values in exactly the right order. Each recursive call only needs its in-order bounds [lo, hi]; an empty range means a missing child.

Complexity

• Time: O(n)
• Space: O(n) for the map plus O(h) recursion

Python

class Solution:
    def buildTree(self, preorder, inorder):
        index_of = {value: i for i, value in enumerate(inorder)}
        next_root = 0   # position in preorder of the next subtree root

        def build(lo, hi):
            # Build the subtree whose values are inorder[lo..hi].
            nonlocal next_root
            if lo > hi:
                return None
            value = preorder[next_root]
            next_root += 1
            node = TreeNode(value)
            mid = index_of[value]
            node.left = build(lo, mid - 1)    # left first: preorder is node, left, right
            node.right = build(mid + 1, hi)
            return node

        return build(0, len(inorder) - 1)

JavaScript

var buildTree = function(preorder, inorder) {
  const indexOf = new Map();
  inorder.forEach((value, i) => indexOf.set(value, i));
  let nextRoot = 0; // position in preorder of the next subtree root

  // Build the subtree whose values are inorder[lo..hi].
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const value = preorder[nextRoot++];
    const node = new TreeNode(value);
    const mid = indexOf.get(value);
    node.left = build(lo, mid - 1);  // left first: preorder is node, left, right
    node.right = build(mid + 1, hi);
    return node;
  };

  return build(0, inorder.length - 1);
};

What the interviewer is checking

The interviewer checks that you understand what each traversal order guarantees, and can turn that into index arithmetic that avoids quadratic slicing.

Mistakes to avoid

• Searching inorder linearly for every root, making it O(n²) on skewed trees.
• Building the right subtree before the left when using a shared preorder pointer.
• Off-by-one errors in the subtree index ranges.
• Very deep (skewed) trees may exceed the recursion limit in some languages; an explicit stack avoids that.

Follow-ups to expect

• Rebuild from inorder and postorder instead. (Root is last; build right first.)
• Why can preorder and postorder alone be ambiguous? (Single children could be either side.)
• Can you do it iteratively? (Stack of nodes awaiting a right child.)

In real software

Serialisation formats and compilers rebuild trees (ASTs, directory structures, scene graphs) from flat traversal orders, and the same split-by-root idea underlies reconstructing parse trees.

Practice next