Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
wb_sunny

Balanced Binary Tree in Python

Balanced Binary Tree In Python

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.

Askpython31 2

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!