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);

• Sumurai8: Could you please include some text with what this code is supposed to do?
• CodeYogi: @Sumurai8 the question is very self explanatory.
• Sumurai8: 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.

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.