☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Construct a BT from Preorder and Inorder

Hard TUF ID 110 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two integer arrays, preorder and inorder, which are the preorder and inorder traversals of the same binary tree. All values are distinct. Build the tree and return its root.

Constraints (LeetCode version): 1 ≤ n ≤ 3000, values in [-3000, 3000], all values unique, and the arrays are guaranteed to come from a real tree. The Java file also accepts empty arrays and returns null.

Example 1

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

        3
       / \
      9   20
         /  \
        15   7
answer = [3, 9, 20, null, null, 15, 7]   // 3 is first in preorder, so it is the root

Example 2

preorder = [-1], inorder = [-1]
answer = [-1]                            // a single node

The key observation

Both approaches rest on the shape of the two arrays. Preorder lists the root, then the whole left subtree, then the whole right subtree. Inorder lists the whole left subtree, then the root, then the whole right subtree:

preorder:  [ root | left subtree (leftSize values) | right subtree ]
inorder:   [ left subtree (leftSize values) | root | right subtree ]

So the root is preorder[0]. Finding that value in inorder tells us how many values sit to its left, leftSize. The left subtree then occupies the next leftSize entries of preorder and the first leftSize entries of inorder; the right subtree takes what remains of each. Each part is again a valid (preorder, inorder) pair of a smaller tree, so recursion finishes the job. The values must be distinct, otherwise “find the root in inorder” would be ambiguous.

Rather than copying subarrays, both methods pass index ranges: pre[preStart..preEnd] is the current subtree’s preorder, and its inorder starts at in[inStart] with the same length.

Approach 1: Brute force, linear search for the root

Intuition. Apply the observation directly: at every call, scan the inorder range from its start until the root value turns up. The scan is the only expensive part.

Algorithm.

  1. If the preorder range is empty (preStart > preEnd), return null.
  2. Create the root from pre[preStart].
  3. Scan in from inStart until in[rootIndex] equals the root value. Let leftSize = rootIndex - inStart.
  4. Build the left child from preorder range preStart + 1 .. preStart + leftSize with inorder starting at inStart.
  5. Build the right child from preorder range preStart + leftSize + 1 .. preEnd with inorder starting at rootIndex + 1.
static TreeNode bruteForce(int[] preorder, int[] inorder) {
    return buildScan(preorder, 0, preorder.length - 1, inorder, 0);
}

// builds the tree whose preorder is pre[preStart..preEnd] and whose inorder starts at in[inStart]
static TreeNode buildScan(int[] pre, int preStart, int preEnd, int[] in, int inStart) {
    if (preStart > preEnd) return null;
    TreeNode root = new TreeNode(pre[preStart]);           // preorder always starts with the root
    int rootIndex = inStart;
    while (in[rootIndex] != root.val) rootIndex++;         // linear search: O(size of this subtree)
    int leftSize = rootIndex - inStart;
    root.left = buildScan(pre, preStart + 1, preStart + leftSize, in, inStart);
    root.right = buildScan(pre, preStart + leftSize + 1, preEnd, in, rootIndex + 1);
    return root;
}

Complexity. Time O(n^2) in the worst case. For a tree that is one long chain of left children, the inorder array is the preorder array reversed, so every root sits at the far end of its range and the scans cost n + (n - 1) + ... + 1. For a balanced tree the scans total O(n log n). Space O(n) for the new nodes plus O(h) recursion depth.

With n = 3000 even the quadratic case is only a few million steps, so this passes, but the lookup is clearly wasted work: the same inorder array is searched over and over.

Approach 2: Optimal, hash map for the root position

Intuition. The values are distinct, so each value has exactly one inorder position. Store value → index in a hash map once, and every root lookup becomes O(1). Nothing else changes.

Algorithm.

  1. Fill inIndex with inorder[i] → i for every i.
  2. Recurse exactly as before, except rootIndex = inIndex.get(rootValue).
static TreeNode optimal(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inIndex = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inIndex.put(inorder[i], i);
    return buildMap(preorder, 0, preorder.length - 1, 0, inIndex);
}

static TreeNode buildMap(int[] pre, int preStart, int preEnd, int inStart, Map<Integer, Integer> inIndex) {
    if (preStart > preEnd) return null;
    TreeNode root = new TreeNode(pre[preStart]);
    int rootIndex = inIndex.get(root.val);
    int leftSize = rootIndex - inStart;
    root.left = buildMap(pre, preStart + 1, preStart + leftSize, inStart, inIndex);
    root.right = buildMap(pre, preStart + leftSize + 1, preEnd, rootIndex + 1, inIndex);
    return root;
}

Dry run on Example 1 (inIndex = {9→0, 3→1, 15→2, 20→3, 7→4}):

call (preStart, preEnd, inStart) root rootIndex leftSize left call right call
(0, 4, 0) 3 1 1 (1, 1, 0) (2, 4, 2)
(1, 1, 0) 9 0 0 (2, 1, 0) empty (2, 1, 1) empty
(2, 4, 2) 20 3 1 (3, 3, 2) (4, 4, 4)
(3, 3, 2) 15 2 0 empty empty
(4, 4, 4) 7 4 0 empty empty

The resulting links are 3 → (9, 20) and 20 → (15, 7), which is the expected tree.

Complexity. Time O(n): one map insertion per value and constant work per node. Space O(n) for the map and the nodes, plus O(h) recursion depth, where h is the tree height (up to n for a chain).

Edge cases and pitfalls

The tests check both methods on the example, a single node, an empty tree, left and right chains, a perfect tree, an uneven tree, a zig-zag, and a 3000-node random tree whose traversals are generated from the tree itself.