Reconstructing a binary tree from its traversal fingerprints

Preorder and inorder together uniquely determine a binary tree — provided all node values are distinct. The intuition is clean: preorder visits root before children, so preorder[0] is always the root of the current subtree. Inorder visits left subtree before root before right subtree, so once you know the root's value you can find its position in inorder and everything to its left forms the left subtree, everything to its right forms the right subtree. That split gives you the sizes of the two subtrees, which in turn tells you exactly where the left and right preorder subsequences are. The recursion is then total.

The diagram above traces the first example: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. Node 3 is the root; its index in inorder is 1, so 1 node goes left (node 9) and 3 nodes go right (15, 20, 7). Preorder then slices accordingly, and the recursion continues.

The problem

Given two integer arrays preorder and inorder — where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree — construct and return the binary tree. Full statement: LeetCode 105.

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.

What the constraints force

The problem says 1 <= preorder.length <= 3000 and all values are unique. Those two facts together determine the design space.

n = 3000 is small enough that O(n²) passes — 9 million operations is nothing for modern hardware. So the naive recursive approach is not a time-limit-exceeded mistake; it just leaves performance on the table. The optimization to O(n) costs you about five extra lines and is the version you should know cold.

All values unique is load-bearing. If duplicates were allowed, the root's position in inorder would be ambiguous, and the problem would be unsolvable without extra information (it is, in fact, a different problem). The uniqueness guarantee is what makes the hash map approach valid: each key appears exactly once.

The constraint -3000 <= preorder[i], inorder[i] <= 3000 means values fit comfortably in an int. No overflow concern anywhere.

Approach 1: recursion with linear inorder search

The direct translation of the observation above: pull preorder[0] as root, call inorder.index(root_val) to find where to split, slice both arrays, recurse.

from typing import List, Optional
 
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]:
        if not preorder or not inorder:
            return None
 
        root_val = preorder[0]
        root = TreeNode(root_val)
 
        root_index = inorder.index(root_val)
 
        left_inorder = inorder[:root_index]
        right_inorder = inorder[root_index + 1:]
 
        left_preorder = preorder[1:1 + len(left_inorder)]
        right_preorder = preorder[1 + len(left_inorder):]
 
        root.left = self.buildTree(left_preorder, left_inorder)
        root.right = self.buildTree(right_preorder, right_inorder)
 
        return root

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if (preorder.Length == 0 || inorder.Length == 0) return null;
 
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);
 
        int rootIndex = Array.IndexOf(inorder, rootVal);
 
        int[] leftInorder = new int[rootIndex];
        int[] rightInorder = new int[inorder.Length - rootIndex - 1];
        Array.Copy(inorder, 0, leftInorder, 0, rootIndex);
        Array.Copy(inorder, rootIndex + 1, rightInorder, 0, rightInorder.Length);
 
        int[] leftPreorder = new int[leftInorder.Length];
        int[] rightPreorder = new int[rightInorder.Length];
        Array.Copy(preorder, 1, leftPreorder, 0, leftInorder.Length);
        Array.Copy(preorder, 1 + leftInorder.Length, rightPreorder, 0, rightInorder.Length);
 
        root.left = BuildTree(leftPreorder, leftInorder);
        root.right = BuildTree(rightPreorder, rightInorder);
 
        return root;
    }
}

Time: O(n²). At each level of the recursion the call to inorder.index (Python) or Array.IndexOf (C#) scans up to n elements. In the worst case — a fully right-skewed tree — the recursion makes n calls and each scans a list of decreasing size: n + (n-1) + ... + 1 = O(n²). Space is also O(n²) because array slicing creates copies at each call.

For n = 3000 this is fine. For n = 100,000 it is not.

Approach 2: hash map + index tracking (O(n))

Two observations cut the cost:

1. Building a {value: inorder_index} hash map once up front turns every root lookup from O(n) to O(1).
2. Instead of slicing arrays, pass boundary indices (left, right) into a nested recursive function. The preorder index advances globally with each root consumed.

from typing import List, Optional
 
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        self.preorder_idx = 0
 
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
 
            root_val = preorder[self.preorder_idx]
            self.preorder_idx += 1
 
            root = TreeNode(root_val)
            root_pos = inorder_map[root_val]
 
            # Left subtree must be built BEFORE right subtree
            # because preorder_idx advances in preorder (root-left-right) order
            root.left = build(left, root_pos - 1)
            root.right = build(root_pos + 1, right)
 
            return root
 
        return build(0, len(inorder) - 1)

public class Solution {
    private Dictionary<int, int> inorderMap;
    private int preorderIdx;
 
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        inorderMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++)
            inorderMap[inorder[i]] = i;
 
        preorderIdx = 0;
        return Build(preorder, 0, inorder.Length - 1);
    }
 
    private TreeNode Build(int[] preorder, int left, int right) {
        if (left > right) return null;
 
        int rootVal = preorder[preorderIdx++];
        TreeNode root = new TreeNode(rootVal);
 
        int rootPos = inorderMap[rootVal];
 
        // Left before right — preorder_idx must stay in sync with preorder traversal order
        root.left = Build(preorder, left, rootPos - 1);
        root.right = Build(preorder, rootPos + 1, right);
 
        return root;
    }
}

Time: O(n). Every node is visited exactly once; each lookup into inorder_map is O(1). Space: O(n) for the hash map plus O(n) worst-case call stack depth (skewed tree). The call stack for a balanced tree is O(log n).

Why left before right is not optional

The preorder_idx is a shared global counter that tracks which element of preorder we consume next. Preorder visits root, then entire left subtree, then entire right subtree. If you call build(root_pos + 1, right) (right subtree) before build(left, root_pos - 1) (left subtree), the counter will consume elements from the right subtree segment while the left subtree is expecting them, and you will build the wrong tree. The ordering of the two recursive calls is semantically load-bearing, not just a style preference.

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

inorder_map = {9:0, 3:1, 15:2, 20:3, 7:4}
preorder_idx = 0

build(left=0, right=4):
  root_val = preorder[0] = 3, preorder_idx -> 1
  root_pos = inorder_map[3] = 1
  root.left = build(left=0, right=0)      <- left subtree of 3
  root.right = build(left=2, right=4)     <- right subtree of 3

  build(left=0, right=0):
    root_val = preorder[1] = 9, preorder_idx -> 2
    root_pos = inorder_map[9] = 0
    root.left = build(left=0, right=-1) -> None
    root.right = build(left=1, right=0) -> None  [left > right]
    return TreeNode(9)

  build(left=2, right=4):
    root_val = preorder[2] = 20, preorder_idx -> 3
    root_pos = inorder_map[20] = 3
    root.left = build(left=2, right=2)   <- left subtree of 20
    root.right = build(left=4, right=4)  <- right subtree of 20

    build(left=2, right=2):
      root_val = preorder[3] = 15, preorder_idx -> 4
      root_pos = inorder_map[15] = 2
      root.left = build(left=2, right=1) -> None
      root.right = build(left=3, right=2) -> None
      return TreeNode(15)

    build(left=4, right=4):
      root_val = preorder[4] = 7, preorder_idx -> 5
      root_pos = inorder_map[7] = 4
      root.left = build(left=4, right=3) -> None
      root.right = build(left=5, right=4) -> None
      return TreeNode(7)

    return TreeNode(20, left=15, right=7)

return TreeNode(3, left=9, right=TreeNode(20, left=15, right=7))

Final tree matches the expected output [3,9,20,null,null,15,7].

Edge cases that actually matter

Single-node tree (preorder = [-1], inorder = [-1]): build(0, 0) fires once, consumes preorder[0], finds root_pos = 0, then calls build(0, -1) and build(1, 0) — both have left > right and return None. Returns TreeNode(-1). Correct.

Completely left-skewed tree (preorder = [1,2,3], inorder = [3,2,1]): The root of each subtree has no right child. The recursion goes n levels deep, each time splitting into a left subtree of size n-1 and a right subtree of size 0. The call stack reaches depth n. For n = 3000, that is 3000 stack frames — well within Python's default 1000 limit after adjusting with sys.setrecursionlimit, but worth being aware of. C# has a much larger default stack depth, so this is not an issue there.

Completely right-skewed tree (preorder = [1,2,3], inorder = [1,2,3]): Symmetric to the above. Same depth concern. In this case every call produces a node with no left child; the right subtree is always the full remaining slice.

All values negative (e.g., preorder = [-3,-9,-20]): the hash map keys are negative integers, which both Python and C# handle without any special treatment. No change to the algorithm.

Values at the constraint boundaries (preorder[i] = -3000 or 3000): nothing special. The values fit in int, hash map lookup is O(1) regardless of value.

Note that duplicates are explicitly ruled out by the problem statement — all values are unique. If duplicates were present, both approaches would be broken in the same way: inorder.index returns the first occurrence, and the hash map would overwrite earlier entries. That problem (LeetCode 889) requires a different approach.

Comparison table

Which one to write

I reach for the hash map version every time. The logic is essentially the same as the naive approach — same recursion structure, same split idea — but building the map once and passing indices instead of sliced arrays is cleaner to reason about and scales to larger inputs without adjustment. The extra state (self.preorder_idx in Python, an instance variable in C#) is a small cognitive cost for a real algorithmic gain.

The naive version is worth understanding because it makes the core idea maximally visible: literally slice the arrays, hand the slices to recursion, trust the base case. If you are explaining the algorithm to someone for the first time, start there. If you are writing the solution, write the hash map version.

The preorder_idx ordering constraint — left subtree before right — is the one detail that bites people. Make it a comment in your code.

How this sits in the trees series

This is the first construction problem in the series. Up to this point (Same Tree, Subtree of Another Tree, Balanced Binary Tree, and the others) the problems have asked you to read a tree and return a value or boolean. Here you are building a tree from scratch. The recursion is the same divide-and-conquer shape, but the return type changes from a scalar to a node, and the recursive calls assign children rather than reducing a comparison.

The underlying pattern is worth naming: divide-and-conquer on traversal subsequences. You have a sequence where one traversal order lets you identify the root, and another lets you partition. That structure appears in several nearby problems.

LeetCode 106 — Construct Binary Tree from Inorder and Postorder Traversal is the direct sibling: inorder still gives you the split, but now postorder gives you the root (last element, not first). The hash map trick transfers directly; only the index logic changes.

LeetCode 889 — Construct Binary Tree from Preorder and Postorder Traversal is harder because inorder is missing. The root's left child is preorder[1], and you use its position in postorder to find the left subtree size. Works only for full binary trees (every node has 0 or 2 children), which is why the problem guarantees that.

LeetCode 297 — Serialize and Deserialize Binary Tree inverts the direction: encode a tree into a string, then reconstruct it. The decoding is exactly the same kind of "pull the next token, recurse" logic as the preorder_idx technique here.

LeetCode 1008 — Construct Binary Search Tree from Preorder Traversal restricts to BST: you know that everything less than root goes left, everything greater goes right. No inorder array needed; the BST property does the splitting. Compare that to 105, where uniqueness and the inorder array do the same job for general trees.