I am trying to return true if the tree is balanced and false if not, I came up with this recursive solution below but I am not correct the correct boolean. I feel that it makes sense to compare the highest height of the tree vs the lower height? Not sure where I am going wrong
function tree (rootNode) {
// Your code here
if (!rootNode) return 0;
if (!rootNode.left && !rootNode.right) return 0;
let minHeigth = 1 + Math.min(tree(rootNode.left), tree(rootNode.right))
let maxHeigth = 1 + Math.max(tree(rootNode.left), tree(rootNode.right))
if(maxHeigth - minHeigth <= 1){
return true
}else{
return false
}
}
My recursive algorithm will be like this.
function isBalanced(rootNode){
if(rootNode == null){
return true;
}
if(checkHeight(rootNode) === -1){
return false;
} else{
return isBalanced(root.left) && isBalanced(root.right);
}
}
and the helper method checkHeight which will check height will be
function checkHeight(rootNode){
if(root ==null){
return 0;
}
let leftHeight=checkHeight(root.left);
let rightHeight=checkHeight(root.right);
if(Math.abs(leftHeight - rightHeight) > 1){
return -1;
}
else{
return Math.max(leftHeight,rightHeight) +1;
}
}
NOTE: This Algo will have the time complexity of O(N)
The main issue is that your function is mixing two things:
If the ultimate purpose is to return a boolean, then you need a different function for getting the height (a number).
Secondly, in determining the height the first two lines of your code show an inconsistency:
null (empty) tree it is determined that its height is 0Yet these two trees have a different height. If a single node (root) is considered to have height 0, then an empty tree has height -1. This is in line with Wikipedia:
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.