46. Construct Binary Tree from Preorder and Inorder Traversal

MediumTree Binary Tree Hash Table Recursion

You are given two integer arrays describing the same binary tree:

preorder: the values in pre-order (node, then left subtree, then right subtree),
inorder: the values in in-order (left subtree, then node, then right subtree).

All values in the tree are unique, which makes the tree fully determined. Rebuild it and return its root.

Example 1

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

Explanation: 1 comes first in pre-order, so it is the root. In the in-order array, 4,2,5 lie to its left (left subtree) and 3,6 to its right (right subtree). Repeat on each side.

Example 2

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

Example 3

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

Constraints

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
All values are unique
inorder is the in-order traversal of the same tree that preorder describes

💡 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