Make delicious recipes!

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.





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal