58.Construct Binary Tree from Preorder and Inorder Traversal

MediumBlind 75Trees · 13/15

Problem

Given two integer arrays preorder and inorder, where preorder is the pre-order traversal of a binary tree and inorder is the in-order traversal of the same tree, reconstruct and return the tree.

All values are unique, which is what makes the reconstruction unambiguous.

Examples

Input:  preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Input:  preorder = [-1], inorder = [-1]
Output: [-1]

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, and preorder is guaranteed to be the pre-order traversal of the tree (likewise for inorder).

💡 Key Insight

The first element of a pre-order range is that subtree's root. Finding the root in the in-order range splits it: everything to its left is the left subtree, everything to its right is the right subtree, and the size of the left part tells us where the left subtree's pre-order range ends. A hash map from value to in-order index makes each split O(1), so the whole build is O(n).

Brute Force (Linear Search + Array Slicing)

TimeO(n²)SpaceO(n²)

Intuition

Apply the split rule directly: take preorder[0] as the root, search for it in inorder to find mid, then copy out the four sub-arrays and recurse. The left subtree has mid nodes, so its pre-order slice is preorder[1 .. mid] and its in-order slice is inorder[0 .. mid - 1].

Algorithm

If preorder is empty, return null.
root = new TreeNode(preorder[0]).
Find mid such that inorder[mid] == root.val (linear scan).
root.left = build(preorder[1 .. mid], inorder[0 .. mid-1]).
root.right = build(preorder[mid+1 .. n-1], inorder[mid+1 .. n-1]).
Return root.

Visualization

preorder = [3 | 9 | 20 15 7]      inorder = [9 | 3 | 15 20 7]
            root left  right                  left root right

left : preorder [9],        inorder [9]         -> leaf 9
right: preorder [20,15,7],  inorder [15,20,7]   -> root 20, left 15, right 7

Code

java

import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int mid = 0;
        while (inorder[mid] != root.val) {
            mid++; // linear search for the root in inorder
        }
        // left subtree has `mid` nodes
        root.left = buildTree(
            Arrays.copyOfRange(preorder, 1, mid + 1),
            Arrays.copyOfRange(inorder, 0, mid));
        root.right = buildTree(
            Arrays.copyOfRange(preorder, mid + 1, preorder.length),
            Arrays.copyOfRange(inorder, mid + 1, inorder.length));
        return root;
    }
}

Complexity

Time: O(n²) — each call does an O(n) search and O(n) copying; a skewed tree has n levels.
Space: O(n²) — copied arrays across all recursion levels in the skewed case.

HashMap + Index Bounds

TimeO(n)SpaceO(n)

Intuition

Two wastes in the brute force: copying arrays and searching linearly. Fix both. Store value -> inorder index in a HashMap once, and describe each subtree by index bounds [inLeft, inRight] into the original inorder array. Because pre-order is "root, entire left subtree, entire right subtree", a single global pointer preIdx that advances by one per created node always points at the next subtree's root — as long as we build the left subtree before the right.

Algorithm

Build indexOf: inorder[i] -> i.
preIdx = 0.
build(inLeft, inRight):
- If inLeft > inRight, return null.
- rootVal = preorder[preIdx++], mid = indexOf.get(rootVal).
- root.left = build(inLeft, mid - 1); root.right = build(mid + 1, inRight).
- Return root.
Return build(0, n - 1).

Dry Run

flowchart TD
    A["build(0,4)<br/>root = 3, mid = 1"] --> B["build(0,0)<br/>root = 9, mid = 0"]
    A --> C["build(2,4)<br/>root = 20, mid = 3"]
    B --> B1["build(0,-1) null"]
    B --> B2["build(1,0) null"]
    C --> D["build(2,2)<br/>root = 15"]
    C --> E["build(4,4)<br/>root = 7"]

preIdx moves 3 -> 9 -> 20 -> 15 -> 7, exactly the pre-order, because the left call always finishes before the right call starts.

Code

java

import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int preIdx = 0;
    private int[] preorder;
    private Map<Integer, Integer> indexOf;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.indexOf = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexOf.put(inorder[i], i);
        }
        return build(0, inorder.length - 1);
    }

    // build the subtree whose in-order values are inorder[inLeft..inRight]
    private TreeNode build(int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIdx++]);
        int mid = indexOf.get(root.val);
        root.left = build(inLeft, mid - 1);   // must be built before right
        root.right = build(mid + 1, inRight);
        return root;
    }
}

Complexity

Time: O(n) — O(n) to fill the map, then O(1) work per node.
Space: O(n) — the map, plus O(h) recursion.

Recursion with Stop ValueOptimal

TimeO(n)SpaceO(h)

Intuition

We can drop the map too. Walk preorder with pointer p and inorder with pointer i. When building a subtree we pass a stop value: the value of the nearest ancestor for which this subtree is on the left. In-order lists the entire left subtree of a node before the node itself, so the left subtree is complete exactly when inorder[i] reaches that ancestor's value. At that point we return null and advance i past it. The left child of node gets stop = node.val; the right child inherits the parent's stop.

Algorithm

p = 0, i = 0.
build(stop):
- If p == n, return null.
- If inorder[i] == stop, increment i and return null (this subtree is finished).
- node = new TreeNode(preorder[p++]).
- node.left = build(node.val); node.right = build(stop).
- Return node.
Return build(sentinel) where the sentinel is a value never present (e.g. Integer.MIN_VALUE, since values are in [-3000, 3000]).

Visualization

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

build(stop=MIN)  create 3            p=1
  build(stop=3)  create 9            p=2
    build(stop=9)   inorder[0]=9 == stop -> i=1, null   (9.left)
    build(stop=3)   inorder[1]=3 == stop -> i=2, null   (9.right)
  build(stop=MIN) create 20          p=3                 (3.right)
    build(stop=20) create 15         p=4
      build(stop=15) inorder[2]=15 -> i=3, null
      build(stop=20) inorder[3]=20 -> i=4, null
    build(stop=MIN) create 7         p=5
      p == n -> null, null

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int p = 0; // next index in preorder
    private int i = 0; // next index in inorder
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return build(Integer.MIN_VALUE); // sentinel: never equals a node value
    }

    // builds a subtree that ends when inorder[i] reaches `stop`
    private TreeNode build(int stop) {
        if (p == preorder.length) {
            return null;
        }
        if (inorder[i] == stop) {
            i++; // consume the ancestor that closes this subtree
            return null;
        }
        TreeNode node = new TreeNode(preorder[p++]);
        node.left = build(node.val); // left subtree ends at node itself
        node.right = build(stop);    // right subtree ends where node's subtree ends
        return node;
    }
}

Complexity

Time: O(n) — each pointer moves forward at most n times, and every call does O(1) work.
Space: O(h) — only the recursion stack; no map.

Complexity Comparison

Approach	Time	Space
Brute Force (Linear Search + Array Slicing)	O(n²)	O(n²)
HashMap + Index Bounds	O(n)	O(n)
Recursion with Stop Value	O(n)	O(h)

Common Pitfalls

Building the right subtree before the left in the pointer-based approaches — preIdx then hands the left subtree's root to the right side.
Off-by-one in slicing: the left subtree has mid nodes, so its pre-order slice is [1, mid + 1), not [1, mid).
Relying on a map when values could repeat — this problem guarantees uniqueness; with duplicates the tree is not uniquely determined.
Making preIdx a local int parameter — Java passes it by value, so increments in the left call are lost to the right call. Use a field (or an array/holder).