Skip to content

Construct from Traversals

The Reverse Problem

Every tree chapter so far has gone in one direction: given a tree, compute something. Now you go the other way. Given the output of traversals, reconstruct the original tree.

This is one of the most-asked interview questions across all companies. The algorithm is elegant, but only if you see the two observations that make it work.

What Two Traversals Give You

A single traversal isn't enough. Preorder [1, 2, 3] could be a right-skewed chain or a left-skewed chain with different structures. You need two traversals to pin down the shape.

The classic combinations:

  • Preorder + Inorder → unique tree (LC 105)
  • Postorder + Inorder → unique tree (LC 106)
  • Preorder + Postorder → unique tree only if the tree is full (every node has 0 or 2 children)

Why does inorder matter? Because inorder tells you which nodes are on the left vs right of any given root. Neither preorder nor postorder alone can tell you that.

Problem 1: Build from Preorder + Inorder (LC 105)

Given:

  • Preorder: [3, 9, 20, 15, 7]
  • Inorder: [9, 3, 15, 20, 7]

Reconstruct the tree.

Observation 1: Preorder Gives You the Root

The first element of preorder is always the root of the tree. Here, 3 is the root.

Observation 2: Inorder Splits Left and Right

Preorder gives the root, inorder splits left and right subtrees

Find 3 in the inorder array. Everything to its left ([9]) belongs to the left subtree. Everything to its right ([15, 20, 7]) belongs to the right subtree.

Inorder: [9, | 3 | , 15, 20, 7]
          ←left→  root  ←──right──→

Now you know: the left subtree has 1 node, the right subtree has 3 nodes.

Observation 3: Preorder Preserves Subtree Order

After the root in preorder, the next 1 element (left subtree size) is the preorder of the left subtree: [9]. The remaining 3 elements are the preorder of the right subtree: [20, 15, 7].

Now recurse: build the left subtree from preorder [9] and inorder [9]. Build the right subtree from preorder [20, 15, 7] and inorder [15, 20, 7].

Step-by-step tree reconstruction from preorder and inorder arrays

Full Trace

Building the tree step by step. preIndex tracks our position in the preorder array.

Step preIndex Root Val Inorder Range Left Inorder Right Inorder
1 0 3 [9, 3, 15, 20, 7] [9] [15, 20, 7]
2 1 9 [9] [] []
3 2 20 [15, 20, 7] [15] [7]
4 3 15 [15] [] []
5 4 7 [7] [] []

Result:

      3
     / \
    9   20
       /  \
      15    7

Manual verification: Preorder of this tree = [3, 9, 20, 15, 7]. Inorder = [9, 3, 15, 20, 7]. Both match the input.

Naive vs Optimized

The naive approach: at each step, scan the inorder array to find the root. That's \(O(n)\) per level, \(O(n^2)\) worst case (skewed tree with \(n\) levels).

The fix: build a hashmap from value → index in the inorder array before starting. Now finding the root's position is \(O(1)\).

The Code

TreeNode* build(vector<int>& preorder, int& preIndex,
                unordered_map<int, int>& inorderIndex,
                int inLeft, int inRight) {
    if (inLeft > inRight) return nullptr;
    int rootVal = preorder[preIndex++];
    TreeNode* root = new TreeNode(rootVal);
    int mid = inorderIndex[rootVal];
    root->left = build(preorder, preIndex, inorderIndex, inLeft, mid - 1);
    root->right = build(preorder, preIndex, inorderIndex, mid + 1, inRight);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inorderIndex;
    for (int i = 0; i < (int)inorder.size(); i++) {
        inorderIndex[inorder[i]] = i;
    }
    int preIndex = 0;
    return build(preorder, preIndex, inorderIndex, 0, (int)inorder.size() - 1);
}

Complexity: \(O(n)\) time, \(O(n)\) space (hashmap + recursion stack).

The key detail: preIndex is passed by reference. As the recursion builds the left subtree, it consumes elements from preorder. When it returns and starts building the right subtree, preIndex is already pointing at the right place. The preorder array acts like a stream — each element is consumed exactly once.

Problem 2: Build from Postorder + Inorder (LC 106)

Given:

  • Postorder: [9, 15, 7, 20, 3]
  • Inorder: [9, 3, 15, 20, 7]

The idea is the same, with two changes:

  1. The root is the last element of postorder (not the first). So read postorder from right to left.
  2. Build the right subtree first, then the left. Because postorder visits left-right-root, reading backwards gives root-right-left.

The Code

TreeNode* buildPost(vector<int>& postorder, int& postIndex,
                    unordered_map<int, int>& inorderIndex,
                    int inLeft, int inRight) {
    if (inLeft > inRight) return nullptr;
    int rootVal = postorder[postIndex--];
    TreeNode* root = new TreeNode(rootVal);
    int mid = inorderIndex[rootVal];
    root->right = buildPost(postorder, postIndex, inorderIndex, mid + 1, inRight);
    root->left = buildPost(postorder, postIndex, inorderIndex, inLeft, mid - 1);
    return root;
}

TreeNode* buildTreeFromPostorder(vector<int>& postorder, vector<int>& inorder) {
    unordered_map<int, int> inorderIndex;
    for (int i = 0; i < (int)inorder.size(); i++) {
        inorderIndex[inorder[i]] = i;
    }
    int postIndex = (int)postorder.size() - 1;
    return buildPost(postorder, postIndex, inorderIndex, 0, (int)inorder.size() - 1);
}

Same complexity: \(O(n)\) time, \(O(n)\) space.

The symmetry: preorder reads left-to-right and builds left subtree first. Postorder reads right-to-left and builds right subtree first. Everything else is identical.

Try It

The starter code has a buildTree function with a TODO. Build the tree from preorder and inorder, then verify by printing the inorder traversal.

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output (inorder of built tree): 9 3 15 20 7

Predict before running: What happens when preorder = [1] and inorder = [1]? preIndex = 0, root = 1, mid = 0, left range = [0, -1] (empty), right range = [1, 0] (empty). Returns a single node. Correct.

Challenge: What if there are duplicate values in the tree? The hashmap approach breaks because two nodes map to the same key. How would you handle duplicates? (Hint: you'd need to fall back to linear search, accepting \(O(n^2)\) worst case.)

Edge Cases to Watch For

  • Duplicate values in the tree: The hashmap from value to index breaks when two nodes have the same value — the second occurrence overwrites the first, producing an incorrect split. You must fall back to linear search, accepting \(O(n^2)\) worst case. LeetCode guarantees distinct values, but real interviews may ask about this.

Problems

Problem Link Difficulty
LC 105 — Construct Binary Tree from Preorder and Inorder Traversal leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal Medium
LC 106 — Construct Binary Tree from Inorder and Postorder Traversal leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal Medium
LC 889 — Construct Binary Tree from Preorder and Postorder Traversal leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal Medium