Check if a tree is balanced - PrismoSkills
Method 2: Since difference between max and min depth of balanced binary tree is 1, that means every leaf will either be at depth d or at depth d-1
We can then check depth at every node which has less than 2 children and if that is not one of d or d-1, then the tree is unbalanced.
However since we do not want to traverse the tree just to find the depth, we can store depth at each leaf in a set. At the end of traversal, if the set contains only two values and those differ by 1, then the tree is balanced.
Read full article from Check if a tree is balanced - PrismoSkills
