Construct Binary Tree from Preorder and Inorder Traversal

MediumBinary Tree · Divide & Conquer🧩 Tree DFS LeetCode #105 ↗Updated Oct 30, 2026

Problem

You are given two arrays, preorder and inorder, which are the pre-order and in-order traversals of the same binary tree with distinct values. Rebuild that tree and return its root.

Inputpre=[3,9,20,15,7], in=[9,3,15,20,7]Output[3,9,20,null,null,15,7]

Inputpre=[-1], in=[-1]Output[-1]

1 ≤ n ≤ 3000 · -3000 ≤ val ≤ 3000 · all values distinct · both arrays describe the same tree

Try it yourself

Java

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

preorder[0] is the root; its position k in inorder splits the rest into left subtree (k values) and right subtree. Recurse on the two halves — the only cost to optimise is finding k.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecursion on Copied Subarrays

Time O(n²)Space O(n²)

Take the root from preorder[0], scan inorder for it to get the left size k, then slice both arrays into new left/right arrays and recurse. On a skewed tree each level copies and scans almost n values, and all those copies are alive on the recursion path.

Java

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int n = preorder.length;
    if (n == 0) return null;
    TreeNode root = new TreeNode(preorder[0]);
    int k = 0;
    while (inorder[k] != root.val) k++; // k = size of left subtree
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, k + 1),
                          Arrays.copyOfRange(inorder, 0, k));
    root.right = buildTree(Arrays.copyOfRange(preorder, k + 1, n),
                           Arrays.copyOfRange(inorder, k + 1, n));
    return root;
}

Mirrors the definition exactly, but copying + scanning is quadratic.

BetterIndex Ranges + Linear Search

Time O(n²)Space O(h)

Never copy: describe a subtree by preStart and the inorder window [inStart, inEnd]. The right subtree's preorder starts at preStart + leftSize + 1. Finding the root is still a linear scan, so a skewed tree costs O(n²) (O(n log n) when balanced).

Java

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode build(int[] pre, int[] in, int preStart, int inStart, int inEnd) {
    if (inStart > inEnd) return null;
    TreeNode root = new TreeNode(pre[preStart]);
    int k = inStart;
    while (in[k] != root.val) k++; // linear search for the root
    int leftSize = k - inStart;
    root.left = build(pre, in, preStart + 1, inStart, k - 1);
    root.right = build(pre, in, preStart + leftSize + 1, k + 1, inEnd);
    return root;
}

No extra arrays, but the repeated scan keeps the worst case quadratic.

OptimalHash Map of Inorder Indices + Preorder Pointer

Time O(n)Space O(n)

Pre-compute value → inorder index so each root is located in O(1). Because recursion builds root, then the whole left subtree, then the right, it consumes preorder strictly left to right — a single moving pointer replaces all preorder index arithmetic.

Java

private int preIdx;
private final Map<Integer, Integer> pos = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    preIdx = 0;
    pos.clear();
    for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
    return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] pre, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(pre[preIdx++]);
    int mid = pos.get(root.val);
    root.left = build(pre, lo, mid - 1);  // left first: matches preorder
    root.right = build(pre, mid + 1, hi);
    return root;
}

Every node is created once with O(1) work — linear time.

Pro tip

Same template solves Postorder + Inorder (LC 106): read postorder from the end and build the right subtree first.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion on Copied Subarrays	`O(n²)`	`O(n²)`
Better	Index Ranges + Linear Search	`O(n²)`	`O(h)`
Optimal	Hash Map of Inorder Indices + Preorder Pointer	`O(n)`	`O(n)`

Common pitfalls

Building the right subtree before the left — the preorder pointer then picks wrong roots.
Off-by-one in the right subtree's preorder start: it is preStart + leftSize + 1.
Relying on distinct values silently — with duplicates the split is ambiguous.

Interview tips

Draw one example and mark the root in both arrays to show the split.
Mention why preorder alone (or inorder alone) can't define a tree uniquely.
Note recursion depth = height: up to 3000 on a skewed tree.

Pattern

Traversal-based reconstruction → root from pre/postorder, split sizes from inorder, recurse.

My notes saved in this browser