Does this code accurately determine if a binary search tree is balanced?

Question

I know I could just look at some examples but I spent a long time trying to get this myself and I'd like to know if I was successful. It passes the tests I gave it, but can I get a sanity check on the code?

Each node is a javascript class with a left & right property that equals either another node or undefined. I also wrote a .hasChildren() method for the Node class which does what it sounds like.

This function is a method of my BinaryTree class, which has another method .height() that takes any node and determines the height of the tree starting with that node. Here is the .isBalanced() method, which also takes a node to start with:

BinaryTree.prototype.isBalanced = function (node = this.root) {
    const rBalanced = (node) => {
    // a node with no children is balanced
    if (!node.hasChildren()) {
      return true
    }

    // get the difference in heights between the branches, using -1 for a missing child
    const left = node.left ? this.height(node.left) : -1
    const right = node.right ? this.height(node.right) : -1

    // if the difference is 1 or less, this node is balanced
    const balanced = Math.abs(left - right) <= 1

    // ensure that every child tree, if it exists, is also balanced
    if (node.left && !node.right) {
      return balanced && rBalanced(node.left)
    }
    if (!node.left && node.right) {
      return balanced && rBalanced(node.right)
    }
    return balanced && rBalanced(node.left) && rBalanced(node.right)
    }
  // a nonexistent tree is balanced (???)
  return node ? rBalanced(node) : true
}

And here is the .height() method just in case:

BinaryTree.prototype.height = function (node = this.root) {
    const rHeight = (node, count) => {
        return Math.max(
            count,
            node.left ? rHeight(node.left, count + 1) : null,
            node.right ? rHeight(node.right, count + 1) : null
        )
    }
    return node ? rHeight(node, 1) : 0
}

EDIT: Here is a jsfiddle with the working code https://jsfiddle.net/jonahsaltzman/u2jrosLm/

Answer 1

The function isBalanced is correct, but there is an inconsistency in the height function, which makes isBalanced return the wrong result. For instance for this tree, it returns false, but true is expected:

      2
     /
    1

The problem in height is that it returns 0 when there is no node. But in isBalanced you use -1 in that case. Compare these two expressions taken from each of these functions:

node ? rHeight(node, 1) : 0

and:

node.left ? this.height(node.left) : -1

This is not consistent. Either a non-existing node has height -1 or it has height 0, but here you have mixed the two. Since the norm is to consider an empty tree as having a height -1, change the code in height:

node ? rHeight(node, 0) : -1
//                  ^^    ^^