Construct Binary Tree from Preorder and Inorder Traversal

Loading...LeetCode

Problem

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]

Pseudocode

- piece together information from two outputs
    - preorder shows left branch first
    - inorder shows left-root-right

Solution

// from solutions, much clearer
var buildTree = function (preorder, inorder) {
  const inorderMap = {};
  let currPreorder = 0;

  inorder.forEach((el, idx) => {
    if (!(el in inorderMap)) {
      inorderMap[el] = idx;
    }
  });

  console.log(inorderMap);

  function dfs(left, right) {
    if (left > right) return null;

    // take currVal

    const currVal = preorder[currPreorder];
    currPreorder++;
    //   console.log(currVal, `indexOf ${preorder.indexOf(currVal)}, ${currPreorder}`)
    const node = new TreeNode(currVal);

    // find idx in inordermap and assign - 1 and + 1 for left and right node respectively
    node.left = dfs(left, inorderMap[currVal] - 1);
    node.right = dfs(inorderMap[currVal] + 1, right);

    return node;
  }

  return dfs(0, inorder.length - 1);
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -