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
}