105. Construct Binary Tree from Preorder and Inorder Traversal

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 105

Problem Statement

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.

Example 1:

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

Example 2:

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.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Approach & Solution Steps

The first element of preorder is the root. Find it in inorder to split into left and right subtrees. Use recursion or a hash map for O(1) lookups in inorder.

Optimal JS Solution

function buildTree(preorder, inorder) {
  const inorderMap = new Map();
  inorder.forEach((val, i) => inorderMap.set(val, i));
  let preIdx = 0;
  function build(inStart, inEnd) {
    if (inStart > inEnd) return null;
    const rootVal = preorder[preIdx++];
    const root = new TreeNode(rootVal);
    const inIdx = inorderMap.get(rootVal);
    root.left = build(inStart, inIdx - 1);
    root.right = build(inIdx + 1, inEnd);
    return root;
  }
  return build(0, inorder.length - 1);
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.