# Challenge – Construct binary tree from array [closed]

Posted on

Problem

A coding challenge to construct a binary tree from an array.

``````class BinaryTreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}

function makeBst(arr){
if(!arr || arr.length <= 1){
return arr;
}
let top = arr[Math.floor(arr.length / 2)];
let node = new BinaryTreeNode(top);
let rightArr = arr.splice(Math.floor(arr.length /2), arr.length);
let leftArr = arr.splice(0, Math.floor(arr.length / 2));
node.right = makeBst(rightArr);
node.left = makeBst(leftArr);
return node;
}

const arr = [1, 2, 3, 4, 5, 6, 7];
makeBst(arr);
``````

The function returns the correct output, and all known edge cases have been accounted for. I would like feedback on cleaning up the conditional logic, as well as help determining the time and space complexity (and the possibility of improving both).

Solution

This solution doesn’t look correct to me. Where’s `2`? Why’s `7` in there twice? Why are `left` and `right` sometimes arrays and sometimes tree nodes?

I guess you meant to use `slice` instead of `splice` (which might explain the fate of that missing `2`), and probably want to exclude the node value in the `right` branch (which might explain the extra `7`).

If I were writing something like this, I’d probably drop that BinaryTreeNode class, since it’s not really doing anything, and use a plain object. Bitwise right shift might be a little less noisy than divide and floor, and you could just do that once since you’re gonna use it three times.

Maybe something like this:

``````function makeBST(a) {
let len = a.length
let mid = len >> 1
return len ? {
value: a[mid],
left: makeBST(a.slice(0, mid)),
right: makeBST(a.slice(mid + 1, len)),
} : null
}
``````

Season to taste with semicolons.