1
\$\begingroup\$
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);
\$\endgroup\$
3
  • \$\begingroup\$ Could you please include some text with what this code is supposed to do? \$\endgroup\$
    – Sumurai8
    Aug 22, 2016 at 15:59
  • \$\begingroup\$ @Sumurai8 the question is very self explanatory. \$\endgroup\$
    – CodeYogi
    Aug 22, 2016 at 16:14
  • \$\begingroup\$ The title of a question is never the first sentence of the question. The question body only contains code. I find that it does not make for a good question if there is no text at all in the question. I am not sure what you are trying to accomplish with having both an inorder and preorder traversal. \$\endgroup\$
    – Sumurai8
    Aug 22, 2016 at 17:20

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.