Skip to main content
CodePeetCodePeet
CodePeet 250

Construct Binary Tree from Preorder and Inorder Traversal

MEDIUMProblemSolveExternal Links

Description

You are given two integer arrays: preorder and inorder. The preorder array represents the preorder traversal of a binary tree (root → left subtree → right subtree), and the inorder array represents the inorder traversal of the same binary tree (left subtree → root → right subtree).

Your task is to reconstruct the original binary tree from these two traversals and return its root node.

Both arrays contain unique values, and every value that appears in one array also appears in the other. The arrays are guaranteed to represent valid traversals of the same binary tree.

The key property that makes reconstruction possible is:

  • Preorder always visits the root first, so the first element of any preorder segment is the root of that subtree.
  • Inorder places the root between its left and right subtrees, so once you know the root, everything to its left in the inorder array belongs to the left subtree, and everything to its right belongs to the right subtree.

Examples

Example 1

Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]

Output: [3, 9, 20, null, null, 15, 7]

Explanation: The first element of preorder is 3, so 3 is the root. In the inorder array, 3 is at index 1. Everything to its left ([9]) forms the left subtree, and everything to its right ([15, 20, 7]) forms the right subtree. Recursively applying this process builds the full tree:

        3
       / \
      9   20
         /  \
        15   7

Example 2

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Explanation: Both arrays have only one element, so the tree is a single node with value -1. There are no left or right children.

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

Editorial

Brute Force

Intuition

The fundamental insight behind constructing a binary tree from preorder and inorder traversals relies on two properties:

  1. Preorder's first element is always the root. In preorder traversal (Root → Left → Right), the very first element we visit is the root of the tree (or subtree).

  2. Inorder splits elements into left and right subtrees. In inorder traversal (Left → Root → Right), once we know which element is the root, everything to the left of the root in the inorder array belongs to the left subtree, and everything to the right belongs to the right subtree.

Imagine you have a box of puzzle pieces (the preorder array) and a reference picture (the inorder array). The first piece in the box is always the center of the current sub-puzzle. You look at the reference picture to see which pieces go on the left side and which go on the right side. Then you repeat for each side.

The brute force approach uses this exact logic, but when searching for the root's position in the inorder array, it scans linearly through the array each time. For each node, this linear search takes O(n) in the worst case, and since we do this for all n nodes, the total becomes O(n²).

Step-by-Step Explanation

Let's trace through with preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]:

Step 1: Take the first element of preorder: 3. This is the root. Initialize preIndex = 0.

Step 2: Search for 3 in inorder. Linear scan: inorder[0]=9 (no), inorder[1]=3 (found at index 1). Left subtree elements = inorder[0..0] = [9]. Right subtree elements = inorder[2..4] = [15, 20, 7].

Step 3: Increment preIndex to 1. Recurse on left subtree (inorder range [0, 0]). Take preorder[1] = 9. Search for 9 in inorder[0..0]: found at index 0. Left of 9 is empty, right of 9 is empty. Node 9 is a leaf.

Step 4: Increment preIndex to 2. Recurse on right subtree (inorder range [2, 4]). Take preorder[2] = 20. Search for 20 in inorder[2..4]: inorder[2]=15 (no), inorder[3]=20 (found at index 3). Left subtree = [15], right subtree = [7].

Step 5: Increment preIndex to 3. Recurse on 20's left subtree (inorder range [2, 2]). Take preorder[3] = 15. Found at inorder[2]. Node 15 is a leaf.

Step 6: Increment preIndex to 4. Recurse on 20's right subtree (inorder range [4, 4]). Take preorder[4] = 7. Found at inorder[4]. Node 7 is a leaf.

Result: The tree is reconstructed as: 3 → left: 9, right: 20 → 20's left: 15, 20's right: 7.

Brute Force — Recursive Construction with Linear Search — Watch how the tree is built node by node. Each step picks the next element from preorder as the root, then linearly searches inorder to split into left and right subtrees.

Algorithm

  1. Maintain a global index preIndex (initially 0) that tracks the current position in the preorder array
  2. Define a recursive function build(inorder, left, right):
    • If left > right, return null (empty subtree)
    • Take the value at preorder[preIndex] as the root value; increment preIndex
    • Create a new tree node with this value
    • Linear search for this value in inorder[left..right] to find its index mid
    • Recursively build the left subtree: build(inorder, left, mid - 1)
    • Recursively build the right subtree: build(inorder, mid + 1, right)
    • Return the node
  3. Call build(inorder, 0, n - 1) and return the root

Code

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int preIndex = 0;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder,
                    int left, int right) {
        if (left > right) return nullptr;

        int rootVal = preorder[preIndex++];
        TreeNode* root = new TreeNode(rootVal);

        // Linear search for root in inorder
        int mid = left;
        for (int i = left; i <= right; i++) {
            if (inorder[i] == rootVal) {
                mid = i;
                break;
            }
        }

        root->left = build(preorder, inorder, left, mid - 1);
        root->right = build(preorder, inorder, mid + 1, right);
        return root;
    }
};
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        self.pre_index = 0

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None

            root_val = preorder[self.pre_index]
            self.pre_index += 1
            root = TreeNode(root_val)

            # Linear search for root in inorder
            mid = left
            for i in range(left, right + 1):
                if inorder[i] == root_val:
                    mid = i
                    break

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)
            return root

        return build(0, len(inorder) - 1)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder,
                           int left, int right) {
        if (left > right) return null;

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        // Linear search for root in inorder
        int mid = left;
        for (int i = left; i <= right; i++) {
            if (inorder[i] == rootVal) {
                mid = i;
                break;
            }
        }

        root.left = build(preorder, inorder, left, mid - 1);
        root.right = build(preorder, inorder, mid + 1, right);
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n nodes, we perform a linear search in the inorder array to find the root's position. In the worst case (a completely skewed tree), the search for each node scans up to n elements, giving O(n) per node × n nodes = O(n²).

For a balanced tree, each level halves the search space, leading to O(n log n) on average. But the worst case remains O(n²).

Space Complexity: O(n)

The recursion stack can go as deep as the height of the tree. In the worst case (skewed tree), the height is n, so the stack uses O(n) space. For a balanced tree, the height is O(log n).

Why This Approach Is Not Efficient

The brute force approach works correctly but has an O(n²) worst-case time complexity due to the linear search in the inorder array for every node. With n up to 3000, this means up to 9 million operations in the worst case — functional but inefficient.

The core waste is that we search for the same values repeatedly in the inorder array. Every time we need to find a root's position in inorder, we scan element by element. But these positions never change — the inorder array is fixed.

The key insight: if we precompute a hash map mapping each value in the inorder array to its index, every root-position lookup becomes O(1) instead of O(n). This eliminates the nested scanning entirely, reducing the total time from O(n²) to O(n).

Optimal Approach - Hash Map for O(1) Lookup

Intuition

The algorithm is identical to the brute force — we still use the same recursive divide-and-conquer strategy. The only change is how we find the root's position in the inorder array.

Instead of scanning linearly each time, we build a hash map before starting the recursion. This map stores every value in the inorder array along with its index. So when we need to find where value 20 sits in the inorder array, we simply look up map[20] and get index 3 instantly.

Think of it like putting sticky-note bookmarks on every page of a book. Without bookmarks, finding a specific page requires flipping through (linear search). With bookmarks, you jump directly to the right page (hash map lookup).

The recursive logic remains unchanged:

  1. Pop the next root from preorder
  2. Look up its position in inorder (now O(1) via hash map)
  3. Recursively build left subtree (elements before the root in inorder)
  4. Recursively build right subtree (elements after the root in inorder)

Since each node is visited exactly once, and the lookup is O(1), the total time becomes O(n).

Step-by-Step Explanation

Let's trace through with preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]:

Step 1: Build hash map from inorder: {9→0, 3→1, 15→2, 20→3, 7→4}. This takes O(n) time and eliminates all future linear searches.

Step 2: preIndex = 0. Root = preorder[0] = 3. Look up map[3] = 1. Left subtree = inorder[0..0], right subtree = inorder[2..4]. O(1) lookup!

Step 3: preIndex = 1. Root = preorder[1] = 9. Look up map[9] = 0. Left = empty, right = empty. Node 9 is a leaf.

Step 4: preIndex = 2. Root = preorder[2] = 20. Look up map[20] = 3. Left subtree = inorder[2..2] = [15], right subtree = inorder[4..4] = [7].

Step 5: preIndex = 3. Root = preorder[3] = 15. Look up map[15] = 2. Leaf node.

Step 6: preIndex = 4. Root = preorder[4] = 7. Look up map[7] = 4. Leaf node.

Result: Same tree as before, but every lookup was O(1) instead of O(n). Total: 5 hash map lookups, each O(1).

Optimal — Hash Map Accelerated Recursive Construction — Watch how the hash map eliminates linear searching. Each node's position in inorder is found in O(1) via the precomputed map, making the entire construction O(n).

Algorithm

  1. Build a hash map indexMap mapping each value in the inorder array to its index
  2. Maintain a global index preIndex (initially 0)
  3. Define a recursive function build(left, right):
    • If left > right, return null
    • Take rootVal = preorder[preIndex]; increment preIndex
    • Create a new node with rootVal
    • Look up mid = indexMap[rootVal] in O(1)
    • Build left subtree: node.left = build(left, mid - 1)
    • Build right subtree: node.right = build(mid + 1, right)
    • Return the node
  4. Call build(0, n - 1) and return the result

Code

#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int preIndex = 0;
    unordered_map<int, int> indexMap;

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

    TreeNode* build(vector<int>& preorder, int left, int right) {
        if (left > right) return nullptr;

        int rootVal = preorder[preIndex++];
        TreeNode* root = new TreeNode(rootVal);

        int mid = indexMap[rootVal];

        root->left = build(preorder, left, mid - 1);
        root->right = build(preorder, mid + 1, right);
        return root;
    }
};
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        index_map = {val: idx for idx, val in enumerate(inorder)}
        self.pre_index = 0

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None

            root_val = preorder[self.pre_index]
            self.pre_index += 1
            root = TreeNode(root_val)

            mid = index_map[root_val]

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)
            return root

        return build(0, len(inorder) - 1)
import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

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

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        int mid = indexMap.get(rootVal);

        root.left = build(preorder, left, mid - 1);
        root.right = build(preorder, mid + 1, right);
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n)

Building the hash map takes O(n) — one pass through the inorder array. The recursive construction visits each node exactly once, and each visit does O(1) work (hash map lookup + node creation). Total: O(n) + O(n) = O(n).

This is a dramatic improvement over the brute force O(n²), achieved simply by trading O(n) space for a hash map.

Space Complexity: O(n)

The hash map stores n entries, taking O(n) space. The recursion stack takes O(h) space where h is the tree height (O(log n) for balanced, O(n) for skewed). The dominant term is O(n) for the hash map.

This is optimal — we must examine every element at least once, so O(n) time is a lower bound. And we need O(n) space to store the tree itself.