Check if a binary tree is balanced
If
difference between max depth and min depth of a tree is more than 1,
then its not balanced. Finding min depth is very much same as max
depth.
Solution
1: Find
max depth and min depth and see if there difference is 1.
/* Finds the maximum depth of given tree */
int maxDepth (Tree node) {
if (node == null) return 0;
return 1 + max (maxDepth(node.left), maxDepth(node.right));
}
/* Finds the minimum depth of given tree */
int minDepth (Tree node) {
if (node == null) return 0;
return 1 + min (minDepth(node.left), minDepth (node.right));
}
/* Finds if a given tree is balanced or not */
boolean isBalanced (Tree root) {
return (maxDeth(root) - minDepth(root) <= 1);
}
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.
|