Find whether if a Given Binary Tree is Balanced?

Objective: Given a binary tree, Find whether if a Given Binary Tree is Balanced?

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one.

Input: A Binary Tree

Output: True and false based on whether tree is balanced or not.

Example:

Balanced Tree Example

Approach :

Naive Approach:
for each node of the tree, get the height of left subtree and right subtree and check the difference , if it is greater than 1, return false.

Complete Code:

Better Solution:

  • Recursion
  • Post order traversal technique
  • Travel all the way down to leaf nodes and then go up.
  • while going up, calculate the left and right subtree height.
  • If the difference between them is greater than 1, return -1.
  • Else Max(leftHeight, rightHeight) +1 .
  • Here you wont actually calculate the height of the subtrees by calling function, instead you will store the height at each level and when you go one level up, you add one to it.
  • So Time complexity is not O(N^2) but it will ne only O(N) but it will have space complexity as O(h) where h is the height of the treeBalanced Tree Example -1
    Complete Code:

    Output:

    Is Tree Balanced : true
    Is Tree Balanced : false
    

__________________________________________________
Top Companies Interview Questions..-

GoogleMicrosoftAmazonFacebookmore..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

9 Responses

  1. Adir says:

    why do you need to chek if the right or left height is -1? it’s possible that the height would be -1?

    • tutorialhorizon says:

      Sorry for the confusion but here Its just a way to represent in this problem when tree is not balanced, return -1. you can use some other value as well

  2. Syed Faisal says:

    if(result>0){
    return true;

    I think the condition must be updated to result >= 0 as a null tree cannot be qualified as unbalanced

  3. disqus_5lcNQavSis says:

    The picture you have made to represent a binary tree is not a functional binary tree… You have a node that has a value greater than 5, but instead of linking it to the right of the ‘5’ node, you’re linking it to the left.

    • hunk_1231 says:

      its totally fine..because the topic is “Find whether if a Given Binary Tree is Balanced?” it’s binary tree and not binary search tree…so it doesn’t matter….he must have done this for the sake of simple example.

  4. hunk_1231 says:

    thank you…this is what exactly i was looking for…god bless you.

  5. Faizaan Shaik says:

    I think the complexity of the first algorithm is NlogN. I got the recurrence relation as T(n) = 1 + n + 2T(n/2)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: