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!