-2
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ "The function returns the correct output, and all known edge cases have been accounted for." Are you sure? You've added one test which doesn't look so good and can't possibly cover all edge cases. Do you have more tests? How did you validate their output? \$\endgroup\$ – Mast Jul 31 at 5:57
  • 2
    \$\begingroup\$ Please verify the correctness of this code. Until then, we have doubts and per the help center we can't help you if the code doesn't work yet. Review is what happens after it works. \$\endgroup\$ – Mast Jul 31 at 6:02
  • 1
    \$\begingroup\$ The result of your "test" returns a tree with the following nodes: 4, 1, 4, 6, 7, 7. That doesn't look like correct output at all. \$\endgroup\$ – Simon Forsberg Jul 31 at 11:21
3
\$\begingroup\$

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.

\$\endgroup\$

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