Create a binary tree from two integer arrays, pOrder and iOrder, where pOrder represents a preorder traversal of a binary tree, and iOrder represents an inorder traversal of the same tree.

binary-tree-from-preorder-inorder.js

// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }

import { TreeNode } from "./ds_v1/BinaryTree.js";

function buildTree(pOrder, iOrder) {
  const indexes = iOrder.reduce(
    (acc, data, index) => ({ ...acc, [data]: index }),
    {}
  );
  const root = buildTreeRec(
    { value: 0 },
    pOrder,
    iOrder,
    indexes,
    0,
    iOrder.length
  );
  return root;
}

// first argument is pIndex, an index in pOrder
// it's a property in an object because it should be shared across all recursion trees
function buildTreeRec(pIndex, pOrder, iOrder, indexes, iFrom, iTo) {
  // we take data from pOrder using pIndex
  const data = pOrder[pIndex.value];

  if (data == null) {
    // we went through the whole pIndex
    return null;
  }

  // then we take index of data in iOrder (indexOf), that is stored in indexes, keyed by data itself
  const indexOf = indexes[data];

  // if indexOf is outside of the current iOrder slice [iFrom, iTo)
  // then it means this data should be handled by some other recursion tree
  // so we just return without incrementing pIndex.value
  if (indexOf < iFrom || indexOf >= iTo) {
    return null;
  }

  // we increment pIndex.value, since we should process each value in pOrder only once
  pIndex.value += 1;

  const node = new TreeNode(data);

  // now we define subsets of iOrder for left and right subtrees of data
  // left subtree of data is to the left of it's position in iOrder
  // right subtree of data is to the right of it's position in iOrder
  // so iFrom and iTo is our current slice of iOrder,
  // left slice would be [iFrom, indexOf)
  const iLeftFrom = iFrom;
  const iLeftTo = indexOf;

  // right slice would be [indexOf + 1, iTo)
  const iRightFrom = indexOf + 1;
  const iRightTo = iTo;

  // and now we recurse on left and right subtree
  node.left = buildTreeRec(pIndex, pOrder, iOrder, indexes, iLeftFrom, iLeftTo);
  node.right = buildTreeRec(
    pIndex,
    pOrder,
    iOrder,
    indexes,
    iRightFrom,
    iRightTo
  );

  return node;
}

export { buildTree };

// tc: O(n)
// sc: O(n) (hash map)