# 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.

Exam­ple:

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:

• Recur­sion
• Post order tra­ver­sal technique
• Travel all the way down to leaf nodes and then go up.
• while going up, cal­cu­late the left and right sub­tree height.
• If the dif­fer­ence between them is greater than 1, return –1.
• Else Max(leftHeight, rightHeight) +1 .
• Here you wont actu­ally cal­cu­late the height of the sub­trees by call­ing func­tion, instead you will store the height at each level and when you go one level up, you add one to it.
• So Time com­plex­ity is not O(N^2) but it will ne only O(N) but it will have space com­plex­ity as O(h) where h is the height of the tree

Bal­anced Tree Exam­ple –1

Com­plete Code:

Out­put:

```Is Tree Balanced : true
Is Tree Balanced : false
```

#### You may also like...

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

if(result>0){
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)