Overview

Given two integer arrays preorder and inorder representing the preorder and inorder traversals of a binary tree, construct and return the binary tree.

The preorder traversal visits: root → left subtree → right subtree. The inorder traversal visits: left subtree → root → right subtree.

Constraints

• preorder.length === inorder.length (1 to 3,000 nodes).
• All values in preorder and inorder are unique.
• Each value in preorder also appears in inorder.
• Return a tree node object: { val, left, right }.

Examples

buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]);
// =>
//       3
//      / \
//     9   20
//        / \
//      15   7

buildTree([1], [1]);
// => { val: 1, left: null, right: null }

Solution

function buildTree(preorder, inorder) {
  if (!preorder.length) return null;
  const rootVal = preorder[0];
  const mid = inorder.indexOf(rootVal);
  return {
    val: rootVal,
    left: buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid)),
    right: buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1)),
  };
}

Resources

• Construct Binary Tree from Preorder and Inorder — LeetCode
• Tree Traversals — Wikipedia