Construct Binary Tree from Preorder and Inorder Traversal

Master this topic with zero to advance depth.

Construct Binary Tree from Preorder and Inorder Traversal

Rebuild tree.

Medium

Approach 1

Level I: Recursive with Linear Search

Intuition

To reconstruct a binary tree from preorder and inorder traversals, we use the fact that the first element in preorder is always the root. We then find this root in the inorder traversal. Everything to the left of the root in inorder belongs to the left subtree, and everything to the right belongs to the right subtree.

Thought Process

root = preorder[0].
Find root index in inorder by iterating (Linear Search).
Slice inorder into leftInorder and rightInorder.
Recursively build left and right subtrees.

⏱ O(N^2) (Search takes O(N) for each of N nodes)💾 O(N) (Recursion stack and array slicing)

Detailed Dry Run

Preorder	Inorder	Root	Left Subtree	Right Subtree
[3,9,20]	[9,3,20]	3	[9]	[20]

java

import java.util.*;

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

    private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) inIndex = i;
        }
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {3, 9, 20, 15, 7}, in = {9, 3, 15, 20, 7};
        TreeNode root = new Main().buildTree(pre, in);
        System.out.println(root.val); // 3
    }
}

Approach 2

Level II: Iterative with Stack

Intuition

We can build the tree iteratively using a stack. The first element of preorder is the root. For subsequent elements, if a node is a left child, it follows its parent in preorder. If it's a right child, it follows some ancestor's left subtree completion.

Logic

Push root to stack.
For each next value: If stack.top().val != inorder[inIndex], it's a left child.
Else, pop from stack until stack.top().val != inorder[inIndex] to find the parent whose right child this value is.

⏱ O(N)💾 O(N)

Detailed Dry Run

Pre:[3,9,20], In:[9,3,20]. Push 3. 3!=9 -> 9 is 3.left. Push 9. 9==9 -> Pop 9, Pop 3. Next is 20. 20 is 3.right.

java

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int inIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = stack.peek();
            if (node.val != inorder[inIndex]) {
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
                    node = stack.pop();
                    inIndex++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

Approach 3

Level III: Optimal (Recursive with Hash Map)

Intuition

Thought Process

Linear search for the root in the inorder array is the primary bottleneck ( $O(N)$ per call). We can optimize this by pre-processing the inorder array into a Hash Map that stores value -> index. This reduces the lookup time to $O(1)$ .

Diagram

Pre: [3, 9, 20, 15, 7]
In:  [9, 3, 15, 20, 7]
Map: {9:0, 3:1, 15:2, 20:3, 7:4}

Step 1: Root = 3 (Index 1 in Inorder)
Left Inorder: [0..0], Right Inorder: [2..4]

⏱ O(N) (Pre-processing takes O(N), every node built in O(1))💾 O(N) (Map stores N elements, recursion stack O(H))

Detailed Dry Run

Call	Range (Start, End)	Root Val	Map Index
Main	(0, 4)	3	1
Left	(0, 0)	9	0
Right	(2, 4)	20	3

java

public class Main {
    int preIndex = 0;
    Map<Integer, Integer> inMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        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 left, int right) {
        if (left > right) return null;
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        root.left = helper(preorder, left, inMap.get(rootVal) - 1);
        root.right = helper(preorder, inMap.get(rootVal) + 1, right);
        return root;
    }
}

⚠️ Common Pitfalls & Tips

Ensure preIndex is accessed globally or passed correctly across recursive calls. Using array slicing (like preorder[1:mid+1]) is easier but often $O(N^2)$ in languages like Python due to copy overhead.

← Previous QuestionBalanced Binary Tree

Next Question →Validate Binary Search Tree

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.