Construct binary tree from inorder and preorder traversal

Question

console.clear();

function cons(inorder, preorder) {
  if (isEmpty(inorder) || isEmpty(preorder)) return null

  if (size(inorder) === 1 && size(preorder) === 1)
    return {val: inorder[0], l: null, r: null};

  var leftSize = inorder.indexOf(head(preorder));

  return {
    val: preorder[0],
    l: cons(take(inorder, leftSize), take(tail(preorder), leftSize)),
    r: cons(drop(inorder, leftSize + 1), drop(tail(preorder), leftSize))
  };
}

function head(xs) {
  return xs[0];
}

function size(xs) {
  return xs.length;
}

function isEmpty(xs) {
  return xs.length === 0;
}

function take(xs, i) {
  return xs.slice(0, i);
}

function drop(xs, i) {
  return xs.slice(i);
}

function tail(xs) {
  return xs.slice(1);
}

var inorder  = [1, 2, 3, 4, 5, 6];
var preorder = [4, 2, 1, 3, 5, 6];


var tree = cons(inorder, preorder);
console.log(tree.r.val === 5);
console.log(tree.l.val === 2);
console.log(tree.r.r.val === 6);
console.log(tree.l.l.val === 1);
console.log(tree.l.r.val === 3);

Answer 1

Algorithm

When inorder and preorder both have a single element, it must be the same value, and the left and right parts in inorder are empty. Therefore the special treatment for size(inorder) === 1 && size(preorder) === 1 is unnecessary, you can simply drop that condition and the algorithm remains correct.

Performance

Although the implementation is elegant, using building blocks common in functional programming, slicing and dicing arrays is not very efficient in JavaScript. The performance could be improved by using indexes of sub-array ranges. It will be ugly, but fast.

Naming

l is the worst variable name ever. Depending on your font, it may be difficult to discern from 1 or |. In this example, I would spell out left and right for the tree branches, naturally.