Course4all

Construct Binary Tree from Preorder and Inorder Traversal

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trees.

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

  1. root = preorder[0].
  2. Find root index in inorder by iterating (Linear Search).
  3. Slice inorder into leftInorder and rightInorder.
  4. 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

PreorderInorderRootLeft SubtreeRight 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

  1. Push root to stack.
  2. For each next value: If stack.top().val != inorder[inIndex], it's a left child.
  3. 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)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)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

CallRange (Start, End)Root ValMap Index
Main(0, 4)31
Left(0, 0)90
Right(2, 4)203
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(N2)O(N^2) in languages like Python due to copy overhead.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionBalanced Binary Tree
Next Question →Validate Binary Search Tree