Is Binary Search tree balanced?
algorithm, binary-tree, data-structures, java, tree
Solution
This solution is not correct. A balanced tree is balanced if its height is `O(lg(n))`, thus it (the height) needs to be smaller then `c*lg(n)` - for some CONSTANT `c`. Your solution assumes this constant is 1.
Note that only a complete tree is of height `lg(n)` exactly.
Look for example on a Fibonacci tree, which is a balanced tree (and is actually the worst case for an AVL tree). However - its height is larger then `lgn` (`~1.44*lg(n)`), and the suggested algorithm will return a fibonacci tree is not balanced.
Problem
This has already been discussed here, but I have an implementation below (which was never discussed in the thread), ``` public boolean isBalanced(BSTNode node) { if(maxHeight() > (int)(Math.log(size())/Math.log(2)) + 1) return false; else return true; } ``` where maxHeight() returns the maximum height of the tree. Basically I am checking if maxHeight > log(n), where n is the number of elements in the tree. Is this a correct solution?