Construct Binary Tree from Preorder and Inorder Traversal

Problem Description

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Examples

Constraints

• 1 ≤ preorder.length ≤ 3000
• inorder.length == preorder.length
• -3000 ≤ preorder[i], inorder[i] ≤ 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

Slicing In-Order Subarrays Using Pre-Order Pivot Nodes

Preorder traversal visits nodes in the order: root, left, right. This means the first element of preorder is always the root of the tree.

Inorder traversal visits nodes: left, root, right. Once you identify the root node value from preorder, you can locate its index in inorder. Everything to the left of this index belongs to the left subtree, and everything to the right belongs to the right subtree.

By recursively slicing the inorder array and advancing our preorder pointer, we can reconstruct the entire tree. To avoid O(n) linear scans of the inorder array to find the root index, we precompute a hash map mapping values to their inorder indices, reducing the lookup to O(1).

Solution 1: Recursive Construction with Map Indexing

Precompute a hash map of the inorder indices. Use helper bounds inStart and inEnd to define the active subtree range in the inorder array.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int preIdx = 0;
    private Map<Integer, Integer> inMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // precompute indices for O(1) lookup
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return helper(preorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);
        int inIdx = inMap.get(rootVal);

        // left subtree corresponds to inorder elements before inIdx
        root.left = helper(preorder, inStart, inIdx - 1);
        // right subtree corresponds to inorder elements after inIdx
        root.right = helper(preorder, inIdx + 1, inEnd);

        return root;
    }
}

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:
        # precompute indices for O(1) lookup
        in_map = {val: i for i, val in enumerate(inorder)}
        pre_idx = 0

        def helper(in_start, in_end):
            nonlocal pre_idx
            if in_start > in_end:
                return None

            root_val = preorder[pre_idx]
            pre_idx += 1
            root = TreeNode(root_val)
            in_idx = in_map[root_val]

            # left subtree corresponds to inorder elements before inIdx
            root.left = helper(in_start, in_idx - 1)
            # right subtree corresponds to inorder elements after inIdx
            root.right = helper(in_idx + 1, in_end)

            return root

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

#include <vector>
#include <unordered_map>

class Solution {
private:
    int preIdx = 0;
    std::unordered_map<int, int> inMap;

    TreeNode* helper(const std::vector<int>& preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;

        int rootVal = preorder[preIdx++];
        TreeNode* root = new TreeNode(rootVal);
        int inIdx = inMap[rootVal];

        // left subtree corresponds to inorder elements before inIdx
        root->left = helper(preorder, inStart, inIdx - 1);
        // right subtree corresponds to inorder elements after inIdx
        root->right = helper(preorder, inIdx + 1, inEnd);

        return root;
    }

public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }
        return helper(preorder, 0, inorder.size() - 1);
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the number of nodes. Building the index map is O(n), and the recursive step visits each node once.
• Space Complexity: O(n). The hash map stores n elements, and the recursion stack uses at most O(h) space.

Where it breaks: This solution relies on all tree node values being unique. If the tree contains duplicate values, the hash map lookup inMap.get(rootVal) becomes ambiguous, and the tree cannot be uniquely reconstructed using only preorder and inorder arrays.

Common Mistakes

• Recreating array slices in Python on every recursion step. While writing self.buildTree(preorder[1 : in_idx+1], inorder[:in_idx]) is concise, it copies arrays, which increases time complexity to O(n²) and wastes memory. Always use pointers to define subarrays.
• Not incrementing the preorder index correctly. The global/outer variable preIdx must be updated sequentially.
• Building the right subtree before the left subtree. Since preorder is root-left-right, the recursive call for root.left must be executed before root.right to align with the order of elements in preorder.

Frequently Asked Questions

Why does this require unique values? If duplicate values exist, the position of the root node in the inorder array cannot be determined uniquely. For example, if both inorder and preorder are [1, 1], we cannot tell if the second 1 is a left or right child.

Can we construct a binary tree from preorder and postorder traversals? Only if the tree is full (every node has 0 or 2 children). For general binary trees, preorder and postorder are not sufficient to uniquely identify whether a single child is a left or right node.

What does this problem test in interviews? It tests your understanding of tree traversals, array partitioning, and recursive construction flow.

← All Problems