Get this book -> Problems on Array: For Interviews and Competitive Programming

Binary tree is a special type of data structure that has collection of elements known as nodes. The topmost node is called parent node. Each node has either zero, one or two child nodes. A node with zero children is called Leaf Node or Terminal Node.

In this article, we will explore the algorithm to check if a Binary Tree is balanced by height or not.

## Terminologies:

**Based on below image let us understand some important terminologies:**

#### 1. Parent :

If any node has a child node on left and/or right then that node is called the parent node to those successor child nodes. All nodes except root node have a parent node.

Example: A is the parent node to node B and C.

#### 2. Level Number:

Each node have a level number in binary tree starting from the root node at level 0. Every child node has parent's level number + 1.

Example: B and C are at Level 1 whereas their parent node A is at Level 0.

#### 3. Degree of a node:

The degree of a node is the number of children of that node. Hence, the degree of leaf node is 0.

Example: Node E in above image has degree 0. However, node A has degree 2.

#### 4. Siblings of Node:

All nodes at the same level with same parent are siblings.

Example: Node G and H are siblings since they are both at Level 3 and have common parent D.

#### 5. Leaf Node:

Any node with no children is leaf or terminal node.

Example: Node E, G, H, I and J are leaf nodes.

#### 6. Edge:

An edge is a line connecting a node to its successor nodes. A binary tree of n nodes has exactly n-1 edges. The reason behind it is that except root node, all other nodes are connected to their parent node via edges.

#### 7. Path:

The sequence of consecutive edges is known as a Path of the node.

Example: The path from node G is node D, node B and node A.

#### 8. Depth:

The length of the path from the root node to the given node is called depth of that node.

Example: Depth of node A is 0 since it is the root node itself.

#### 9. Height of the tree:

It is the length from the root node till the node of maximum depth. If the height of any tree is "h" then it can have h nodes or at most 2h-1 nodes.

The height of a binary tree with n nodes is at least log2(n+1) and at most n.

Example: Height of above tree is 3.

**Below is the figure of the binary tree.**

Here, Node 1 is the root node. The left-subtree consists of node 2, 4 and 7. The right subtree consists of node 3, 5, 6 and 8. Node 1 has two successors node 2 and 3. Whereas, node 7, 5 and 8 have no successor nodes. Hence, they have empty sub-trees.

The root pointer points to the root node. Further, every element has a data element with left pointer, pointing to the left node and right pointer, pointing to the right node respectively.

## Checking if a binary tree is balanced:

A tree is said to be balance if:

- The left subtree is balanced for each node.
- Right subtree is also balanced for each node.
- The absolute height difference of left and right subtree is not more than 1.

Further,all empty trees are always height balanced.

### Algorithm:

Step 1: Start

Step 2: If the node is NULL then return 0.

Step 3: If left sub tree is not balanced then return -1.

Step 4: If the right sub tree is not balanced then return -1.

Step 5: If the absolute difference between height of left and right subtree is greater than 1,return -1 else return maximum out of left and right subtree's height + 1.

Step 6: End.

**Example:**

Considering the binary tree below,

**Firstly, our node is not NULL.**

**Hence, we proceed to check the height of left subtree first.**

**1.** For the root node, the height of its left subtree is 2 (from node 1 to node 2 **and** node 2 to node 4). Similarly, the height of the right subtree is 1 (from node 1 to node 3). So, absolute difference in the height of left and right subtree is 1.

**Hence, satisfying the condition that absolute difference of the height of left and right subtree is smaller than or equal to 1.**

**2.** Similarly,for the node 2 the height of its left subtree is 1 (node 2 to node 4) and height of right subtree is also 1 (node 2 to node 5). Hence, the absolute difference of their heights is 0.

**Hence, satisfying the condition that absolute difference of the height of left and right subtree is smaller than or equal to 1.**

**3.** For node 4, node 5 and node 3 the absolute difference in their left and right subtrees is 0 since they do not have any children nodes.

**Hence, satisfying the condition that absolute difference of the height of left and right subtree is smaller than or equal to 1.**

This way all nodes satisfy the required condition. Hence, our binary tree is balanced.

**Let us implement it via code :**

```
//Assuming the node of the binary tree is already defined
// Function to check if a binary tree is balanced by height
class sol{
public:
// firstly, pass the root as argument to "balanced" function
int balanced(Node* root)
{
// if the root is NULL return 0
if(root==NULL)return 0;
//check if the left subtree's height is balanced. If no then return -1
int leftheight = balanced(root ->left);
if(leftheight == -1)return -1;
//check if the right subtree's height is balanced. If no then return -1
int rightheight = balanced(root->right);
if(rightheight == -1)return -1;
//if absolute difference of left subtree's height and right subtree's height > 1 then return -1
if(abs(rightheight-leftheight)>1) return -1;
// return maximum out of left subtree's height and right subtree's height + 1
return max(leftheight,rightheight)+1;
}
bool bal(Node *root) {
return balanced(root) != -1;
}
};
```

**The time complexity of this approach is O(n).**

Hence using the above described approach in Opengenus article you can easily find out if a binary tree is balanced by height or not.