In this article, we will study balanced binary trees and we will try to implement a program in Python to determine if a binary tree is balanced or not. To read this article, you should be familiar with the concept of binary trees.

## What is a Balanced Binary Tree?

A balanced binary tree is defined as a binary tree in which at every node, its left sub-tree and right sub-tree have an equal height or their height differ by just 1.

In other words, if we consider any node of the tree as the root of a tree, then the heights of its left sub-tree and right sub-tree should never differ by more than 1.

## How to check if a Binary Tree is Balanced or not?

As per the definition, the height of the left subtree and right subtree should not be greater than one at any node.

So if we consider a tree to be balanced at any node, we will have to find the height of its left sub-tree and right sub-tree.

Then we will check the difference in the heights. If the difference comes out to be greater than 1 at any node, we will declare that the tree is not balanced. The following is the algorithm for this procedure:

Algorithm CheckBalancedBinaryTree: Input: Root Node of the binary tree. Output:True if binary tree is balanced and False otherwise. Start. 0.If tree is empty, return True. 1. Check the height of left sub-tree. 2.Check the height of right sub-tree. 3.If difference in height is greater than 1 return False. 4.Check if left sub-tree is balanced. 5.Check if right sub-tree is balanced. 6. If left sub-tree is balanced and right sub-tree is also balanced, return True. End

We have figured out the algorithm for checking if the binary tree is balanced but we don’t know how to calculate the height of tree and sub trees. So We will first implement a program to find the height of tree if the root node is given and then we will implement the above algorithm.

## How to find the height of a balanced binary tree?

To find the height of a binary tree, we can just keep in mind the following points.

- If the root is empty, then the height of the tree will be 0.
- If the root is not empty, then the height of the tree will be equal to the maximum height of the left sub-tree of the root and right sub-tree of the root added 1.

Keeping in mind the above points, The algorithm for finding the height of the tree is:

**Algorithm height(tree):**- Input: Root of the tree
- Output: Height of the tree
- Start.
- 1.If the root is None, Return 0.
- 2.Find the height of the left subtree.//height(root.leftChild)
- 3.Find the height of the right subtree .//height(root.rightChild)
- 4.Find the maximum value in 2 and 3 and add 1 to it.
- End

Now we will implement the above algorithm and execute it for the following binary tree.

## Program to find the height of a binary tree

Following is the code for finding height of a binary tree.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root def height(root): #if root is None return 0 if root==None: return 0 #find height of left subtree hleft=height(root.leftChild) #find the height of right subtree hright=height(root.rightChild) #find max of hleft and hright, add 1 to it and return the value if hleft>hright: return hleft+1 else: return hright+1 root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing the height of the binary tree.") print(height(root))

Output: Printing the height of the binary tree. 3

Now, we know how to find the height of a binary tree. So we will now implement the algorithm to check if a binary tree is balanced or not for above given binary tree.

## Program to check if a Binary Tree is Balanced or not

Following program has been implemented to check if binary tree is balanced or not.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root def height(root): #if root is None return 0 if root==None: return 0 #find height of left subtree hleft=height(root.leftChild) #find the height of right subtree hright=height(root.rightChild) #find max of hleft and hright, add 1 to it and return the value if hleft>hright: return hleft+1 else: return hright+1 def CheckBalancedBinaryTree(root): #if tree is empty,return True if root==None: return True #check height of left subtree lheight= height(root.leftChild) rheight = height(root.rightChild) #if difference in height is greater than 1, return False if(abs(lheight-rheight)>1): return False #check if left subtree is balanced lcheck=CheckBalancedBinaryTree(root.leftChild) #check if right subtree is balanced rcheck=CheckBalancedBinaryTree(root.rightChild) #if both subtree are balanced, return True if lcheck==True and rcheck==True: return True root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing True if binary tree is balanced:") print(CheckBalancedBinaryTree(root))

Output: Printing True if binary tree is balanced: True

As the binary tree in our example is balanced, the program has printed True. You can check it for unbalanced binary trees by modifying the program to insert new values.

## Conclusion

In this article, we have studied the concept of a balanced binary tree. We have also discussed the algorithms for finding the height of a binary tree and checking if a binary tree is balanced or not. Stay tuned for more informative articles.

Happy Learning!