Construct Binary Tree from Preorder and Inorder Traversal

Medium Problem 77 of 151 Java and Python

Problem

Given two integer arrays preorder and inorder, the preorder and inorder traversals of the same binary tree with unique values, construct and return the tree.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 3000
All values are unique.

Explanation

The first value of preorder is the root. Find it in inorder: everything to its left is the left subtree, everything to its right is the right subtree. The sizes tell you how to split preorder too.

Recurse on both halves. A hash map from value to inorder index makes each lookup O(1).

Approach 1 · Naive

Recursion with linear search

Time O(n²) worst case
Space O(h)

Same recursion, but find the root in inorder by scanning.

The root is preorder[pre]; scan inorder[lo..hi] for it to get mid.
Left size = mid - lo. Build the left subtree from the next size preorder values, then the right subtree.

Java

class Solution {
    private int pre = 0;

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

    private TreeNode build(int[] preorder, int[] inorder, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre++]);
        int mid = lo;
        while (inorder[mid] != root.val) {
            mid++;
        }
        root.left = build(preorder, inorder, lo, mid - 1);
        root.right = build(preorder, inorder, mid + 1, hi);
        return root;
    }
}

Python

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

Approach 2 · Optimal

Recursion with an index map

Time O(n)
Space O(n)

Precompute each value's inorder index, and consume preorder left to right with a shared pointer.

Map value → inorder index.
build(lo, hi): if lo > hi, return null. Take the next preorder value as the root; mid = index[root].
Build left = build(lo, mid - 1) before right = build(mid + 1, hi), matching preorder.

Java

import java.util.*;

class Solution {
    private int pre = 0;
    private final Map<Integer, Integer> index = new HashMap<>();

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

    private TreeNode build(int[] preorder, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre++]);
        int mid = index.get(root.val);
        root.left = build(preorder, lo, mid - 1);
        root.right = build(preorder, mid + 1, hi);
        return root;
    }
}

Python

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        index = {value: i for i, value in enumerate(inorder)}
        values = iter(preorder)

        def build(lo, hi):
            if lo > hi:
                return None
            root = TreeNode(next(values))
            mid = index[root.val]
            root.left = build(lo, mid - 1)
            root.right = build(mid + 1, hi)
            return root

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

Complexity compared

Approach	Time	Space
Naive Recursion with linear search	O(n²) worst case	O(h)
Optimal Recursion with an index map	O(n)	O(n)

Key takeaways

The same split works for postorder + inorder; there the root is the last value and you build the right subtree first.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem