Construct Binary Tree from Preorder and Inorder Traversal

MediumTree Binary Tree Hash Table Recursion

A legacy analytics system exported its decision tree as two flat lists instead of a proper tree structure:

preorder lists the node values in pre-order: a node first, then its left subtree, then its right subtree,
inorder lists them in in-order: the left subtree first, then the node, then the right subtree.

Every value in the tree is unique, so the two lists describe exactly one tree. Rebuild it and return its root.

Example 1

Input: preorder = [10,5,2,7,15,20], inorder = [2,5,7,10,15,20]
Output: [10,5,15,2,7,null,20]

Explanation: 10 comes first in pre-order, so it is the root. In inorder, 2,5,7 lie to its left and 15,20 to its right, which splits both lists into the two subtrees. Repeat on each part.

Example 2

Input: preorder = [4,8], inorder = [8,4]
Output: [4,8]

Explanation: 8 comes before the root 4 in inorder, so it is the left child.

Example 3

Input: preorder = [1,2,3], inorder = [1,3,2]
Output: [1,null,2,3]

Explanation: Nothing comes before 1 in inorder, so the root has no left subtree.

Constraints

Both arrays have the same length, between 1 and 3000.
Values are unique integers from -3000 to 3000.
inorder is the in-order traversal of the same tree that preorder describes in pre-order.

💡 Hint 1

The first value in preorder is always the root. Where does that value sit in inorder, and what does that split tell you?

💡 Hint 2

Everything left of the root in inorder is the left subtree, everything right of it is the right subtree. The sizes of those parts tell you how to slice preorder too.

💡 Hint 3

Searching inorder for every root is O(n) each time. Precompute a map from value to in-order index, and consume preorder with a single moving pointer instead of slicing arrays.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Pre-order lists every root before its subtrees, so reading preorder left to right hands out roots in exactly the order a recursive build needs them. Build a hash map from each value to its index in inorder. The recursive helper build(lo, hi) constructs the subtree whose values occupy inorder[lo..hi]: take the next value from preorder as the root, look up its in-order index mid, then build the left subtree from lo..mid-1 first (that is the order pre-order uses) and the right subtree from mid+1..hi. An empty range returns null.

Time O(n)Space O(n) for the map, plus O(h) recursion

function buildTree(preorder, inorder) {
  const indexOf = new Map(inorder.map((v, i) => [v, i]));
  let next = 0;
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const val = preorder[next++];
    const mid = indexOf.get(val);
    const node = new TreeNode(val);
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  };
  return build(0, inorder.length - 1);
}

class Solution {
    private final Map<Integer, Integer> indexOf = new HashMap<>();
    private int[] preorder;
    private int next = 0;

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

    private TreeNode build(int lo, int hi) {
        if (lo > hi) return null;
        int val = preorder[next++];
        int mid = indexOf.get(val);
        TreeNode node = new TreeNode(val);
        node.left = build(lo, mid - 1);
        node.right = build(mid + 1, hi);
        return node;
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit