Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find whether if a Given Binary Tree is Balanced?

Objec­tive: Given a binary tree, Find whether if a Given Binary Tree is Balanced?

What is bal­anced Tree: A bal­anced tree is a tree in which dif­fer­ence between heights of sub-trees of any node in the tree is not greater than one.

Input: A Binary Tree

Out­put: True and false based on whether tree is bal­anced or not.


Balanced Tree Example

Bal­anced Tree Example

Approach :

Naive Approach:
for each node of the tree, get the height of left sub­tree and right sub­tree and check the dif­fer­ence , if it is greater than 1, return false.

Bet­ter Solution:

You may also like...

  • Adir

    why do you need to chek if the right or left height is –1? it’s pos­si­ble that the height would be –1?

    • tuto­ri­al­hori­zon

      Sorry for the con­fu­sion but here Its just a way to rep­re­sent in this prob­lem when tree is not bal­anced, return –1. you can use some other value as well

  • Syed Faisal

    return true;

    I think the con­di­tion must be updated to result >= 0 as a null tree can­not be qual­i­fied as unbalanced

    • hunk_1231

      totally agree 🙂

  • disqus_5lcNQavSis

    The pic­ture you have made to rep­re­sent a binary tree is not a func­tional binary tree… You have a node that has a value greater than 5, but instead of link­ing it to the right of the ‘5’ node, you’re link­ing it to the left.

    • hunk_1231

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

      • disqus_5lcNQavSis

        I didn’t notice that. I thought it read Binary Search Tree. My apolo­gies to the OP.

  • hunk_1231

    thank you…this is what exactly i was look­ing for…god bless you.

  • Faizaan Shaik

    I think the com­plex­ity of the first algo­rithm is NlogN. I got the recur­rence rela­tion as T(n) = 1 + n + 2T(n/2)