{"id":12573,"date":"2021-02-11T14:02:44","date_gmt":"2021-02-11T14:02:44","guid":{"rendered":"https:\/\/www.askpython.com\/?p=12573"},"modified":"2021-02-17T11:45:21","modified_gmt":"2021-02-17T11:45:21","slug":"balanced-binary-tree","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/balanced-binary-tree","title":{"rendered":"Balanced Binary Tree in Python"},"content":{"rendered":"\n

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.<\/a><\/p>\n\n\n\n

What is a Balanced Binary Tree?<\/h2>\n\n\n\n

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. <\/p>\n\n\n\n

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.<\/p>\n\n\n\n

How to check if a Binary Tree is Balanced or not?<\/h2>\n\n\n\n

As per the definition, the height of the left subtree and right subtree should not be greater than one at any node. <\/p>\n\n\n\n

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. <\/p>\n\n\n\n

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:<\/p>\n\n\n

\nAlgorithm CheckBalancedBinaryTree:\nInput: Root Node of the binary tree.\nOutput:True if binary tree is balanced and False otherwise.\nStart.\n0.If tree is empty, return True.\n1. Check the height of left sub-tree.\n2.Check the height of right sub-tree.\n3.If difference in height is greater than 1 return False.\n4.Check if left sub-tree is balanced.\n5.Check if right sub-tree is balanced.\n6. If left sub-tree is balanced and right sub-tree is also balanced, return True.\nEnd\n<\/pre><\/div>\n\n\n
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.<\/p>\n\n\n\n
How to find the height of a balanced binary tree?<\/h2>\n\n\n\n
To find the height of a binary tree, we can just keep in mind the following points.<\/p>\n\n\n\n
  • If the root is empty, then the height of the tree will be 0.<\/li>
  • 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.<\/li><\/ul>\n\n\n\n
    Keeping in mind the above points, The algorithm for finding the height of the tree is:<\/p>\n\n\n\n
    • Algorithm height(tree):<\/strong><\/li>
    • Input: Root of the tree<\/li>
    • Output: Height of the tree<\/li>
    • Start.<\/li>
    • 1.If the root is None, Return 0.<\/li>
    • 2.Find the height of the left subtree.\/\/height(root.leftChild)<\/li>
    • 3.Find the height of the right subtree .\/\/height(root.rightChild)<\/li>
    • 4.Find the maximum value in 2 and 3 and add 1 to it.<\/li>
    • End<\/li><\/ul>\n\n\n\n
      Now we will implement the above algorithm and execute it for the following binary tree.<\/p>\n\n\n\n
      \"Askpython31<\/figure><\/div>\n\n\n\n
      Program to find the height of a binary tree<\/h2>\n\n\n\n
      Following is the code for finding height of a binary tree.<\/p>\n\n\n
      \nclass BinaryTreeNode:\n  def __init__(self, data):\n    self.data = data\n    self.leftChild = None\n    self.rightChild=None\n    \ndef insert(root,newValue):\n    #if binary search tree is empty, make a new node and declare it as root\n    if root is None:\n        root=BinaryTreeNode(newValue)\n        return root\n    #binary search tree is not empty, so we will insert it into the tree\n    #if newValue is less than value of data in root, add it to left subtree and proceed recursively\n    if newValue<root.data:\n        root.leftChild=insert(root.leftChild,newValue)\n    else:\n        #if newValue is greater than value of data in root, add it to right subtree and proceed recursively\n        root.rightChild=insert(root.rightChild,newValue)\n    return root\n\ndef height(root):\n    #if root is None return 0\n        if root==None:\n            return 0\n        #find height of left subtree\n        hleft=height(root.leftChild)\n        #find the height of right subtree\n        hright=height(root.rightChild)  \n        #find max of hleft and hright, add 1 to it and return the value\n        if hleft>hright:\n            return hleft+1\n        else:\n            return hright+1\n    \nroot= insert(None,15)\ninsert(root,10)\ninsert(root,25)\ninsert(root,6)\ninsert(root,14)\ninsert(root,20)\ninsert(root,60)\nprint("Printing the height of the binary tree.")\nprint(height(root))\n<\/pre><\/div>\n\n
      \nOutput:\n\nPrinting the height of the binary tree.\n3\n<\/pre><\/div>\n\n\n
      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.<\/p>\n\n\n\n
      Program to check if a Binary Tree is Balanced or not<\/h2>\n\n\n\n
      Following program has been implemented to check if binary tree is balanced or not.<\/p>\n\n\n
      \nclass BinaryTreeNode:\n  def __init__(self, data):\n    self.data = data\n    self.leftChild = None\n    self.rightChild=None\n    \ndef insert(root,newValue):\n    #if binary search tree is empty, make a new node and declare it as root\n    if root is None:\n        root=BinaryTreeNode(newValue)\n        return root\n    #binary search tree is not empty, so we will insert it into the tree\n    #if newValue is less than value of data in root, add it to left subtree and proceed recursively\n    if newValue<root.data:\n        root.leftChild=insert(root.leftChild,newValue)\n    else:\n        #if newValue is greater than value of data in root, add it to right subtree and proceed recursively\n        root.rightChild=insert(root.rightChild,newValue)\n    return root\n\ndef height(root):\n    #if root is None return 0\n        if root==None:\n            return 0\n        #find height of left subtree\n        hleft=height(root.leftChild)\n        #find the height of right subtree\n        hright=height(root.rightChild)  \n        #find max of hleft and hright, add 1 to it and return the value\n        if hleft>hright:\n            return hleft+1\n        else:\n            return hright+1\n\ndef CheckBalancedBinaryTree(root):\n    #if tree is empty,return True\n    if root==None:\n        return True\n    #check height of left subtree\n    lheight= height(root.leftChild)\n    rheight = height(root.rightChild)\n    #if difference in height is greater than 1, return False\n    if(abs(lheight-rheight)>1):\n        return False\n    #check if left subtree is balanced\n    lcheck=CheckBalancedBinaryTree(root.leftChild)\n    #check if right subtree is balanced\n    rcheck=CheckBalancedBinaryTree(root.rightChild)\n    #if both subtree are balanced, return True\n    if lcheck==True and rcheck==True:\n        return True\n\n    \n    \nroot= insert(None,15)\ninsert(root,10)\ninsert(root,25)\ninsert(root,6)\ninsert(root,14)\ninsert(root,20)\ninsert(root,60)\nprint("Printing True if binary tree is balanced:")\nprint(CheckBalancedBinaryTree(root))\n<\/pre><\/div>\n\n
      \nOutput:\n\nPrinting True if binary tree is balanced:\nTrue\n<\/pre><\/div>\n\n\n
      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.<\/p>\n\n\n\n
      Conclusion<\/h2>\n\n\n\n
      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.<\/p>\n\n\n\n
      Happy Learning!<\/p>\n\n\n","protected":false},"excerpt":{"rendered":"
      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 […]<\/p>\n","protected":false},"author":20,"featured_media":12574,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-12573","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12573","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=12573"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12573\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/12574"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=12573"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=12573"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=12573"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}