{"id":1178,"date":"2023-12-25T21:00:00","date_gmt":"2023-12-25T21:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1178"},"modified":"2023-12-28T07:22:44","modified_gmt":"2023-12-28T07:22:44","slug":"balanced-binary-tree","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/balanced-binary-tree\/","title":{"rendered":"Check for Balanced Binary Tree (C++, Java, Python)"},"content":{"rendered":"\n<p>A balanced binary tree is an important data structure in optimizing search, insert, and delete operations. In this article, we will explore the concept of balanced binary trees, two different approaches to determining whether a given binary tree is height-balanced or not, and how to implement the solution.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Balanced Binary Tree Problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Balanced Binary Tree problem, we are given a binary tree and we have to check whether the given binary tree is balanced or not. A binary tree is balanced when the depth of every node\u2019s left and right subtrees differs by at most one.<\/strong><\/p>\n\n\n\n<p>Check the example of a balanced binary tree below:\u00a0<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/q4FGRr8nipjFzxuT16SNIzohHddckO8GuAAmcExkGAdoCeQU5M7AQPpYFINRTX9cdMAEJpm6erCAhVZrgZT9FvdfSZ3i0Ra8A4yWRUgSne3A8jsAodeWuxfgq6-jCn-5SMuvW0KtGhrYySLmPguHiP0\" alt=\"Balanced Binary Tree\"\/><\/figure>\n<\/div>\n\n\n<p>As we can see the difference in heights for every subtree is not more than 1, it is balanced.<\/p>\n\n\n\n<p>In the simplest naive approach, we will check the height of the left and right subtree for every node present in the tree for this we will traverse the tree recursively to calculate the height of the left and right subtree from every node, and whenever the condition of balanced binary tree violates, we will return false.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/o8Fi3E2HnPxX-AoXTwQaJ1SGI1AtIL2Vuq0Lpu6d01IikeiJJdxuMDrA1rHRdM2vkY8nikNJtyX_bdEwpC6BS99DTWu_lKZRE-ICoVb8KVM-uFmQEyVm0H1heuQzvuAHQqQZnqVfqzu8bTrEXEPAiSI\" alt=\"Naive Approach to check for balanced binary tree\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will start traversing the tree from <strong>Node 3: <\/strong>left height = 1 and right height = 2 absolute difference is (2-1) = 1<\/li>\n\n\n\n<li><strong>Node 6: <\/strong>left height = 0 and right height = 0 absolute difference is (0-0) = 0<\/li>\n\n\n\n<li><strong>PostOrder of Node 6<\/strong>, the left subtree (null) gives true &amp; right subtree (null) gives true, as both are true, return true.<\/li>\n\n\n\n<li><strong>Node 7: <\/strong>left height = 1 and right height = 1 absolute difference is (1-1) = 0<\/li>\n\n\n\n<li><strong>Node 1: <\/strong>left height = 0 and right height = 0 absolute difference is (0-0) = 0<\/li>\n\n\n\n<li><strong>PostOrder of Node 1<\/strong>, the left subtree (null) gives true &amp; right subtree (null) gives true, as both are true, return true.<\/li>\n\n\n\n<li><strong>Node 0: <\/strong>left height = 0 and right height = 0 absolute difference is (0-0) = 0.<\/li>\n\n\n\n<li><strong>PostOrder of Node 0<\/strong>, the left subtree (null) gives true &amp; right subtree (null) gives true, as both are true, return true.<\/li>\n\n\n\n<li><strong>PostOrder of Node 7<\/strong>, the left subtree (1) gives true &amp; right subtree (0) gives true, as both are true, return true.<\/li>\n\n\n\n<li><strong>PostOrder of Node 3<\/strong>, the left subtree (6) gives true &amp; right subtree (7) gives true, as both are true, return true.<\/li>\n<\/ul>\n\n\n\n<p>Overall all nodes are returning true which means our binary tree is a balanced binary tree. You can learn how to <a href=\"https:\/\/favtutor.com\/blogs\/binary-tree-height\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/binary-tree-height\">find the height of a binary tree using recursion<\/a> as well.<\/p>\n\n\n\n<p>The time complexity for this naive approach is O(N*N) because for every node height function is called which takes O(N) time hence every node is visited multiple times. The space complexity for this approach is O(1) (extra space) + O(H) recursive stack space where H is the height of the tree.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Post-order Traversal to Check Binary Tree is Balanced or Not<\/strong><\/h2>\n\n\n\n<p><strong>In the post-order traversal approach to check for a balanced binary tree, we will use the post-order traversal to recursively traverse the left subtree and the right subtree.<\/strong><\/p>\n\n\n\n<p>From this, we will calculate the height of the current node as the maximum height of its left and right subtrees, plus 1. Check if the current node is balanced by comparing the heights of its left and right subtrees. The tree is not balanced if the absolute difference is greater than 1.<\/p>\n\n\n\n<p>Here is the step-by-step guide to doing it practically:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>First, we will declare the base case of our recursive function that if the current node equals NULL, it means we have reached the end of a branch. In this case, the height of this subtree is 0.<\/li>\n\n\n\n<li>Now we will start traversing the tree recursively with post-order calculating the height of the root node and returning to its previous call.<\/li>\n\n\n\n<li>While obtaining each node&#8217;s post order, we will check the condition of the balance tree as we have the height of the left and right subtree.<\/li>\n\n\n\n<li>If the tree is balanced we will simply return the height of the subtree otherwise we will return -1.<\/li>\n\n\n\n<li>If subtree is not balanced we will simply return -1.<\/li>\n<\/ol>\n\n\n\n<p>Let\u2019s see an example of the same:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/VPsJMjxH5rkfEgplNG-Eknj6bZvTbf78-_CnymHnuvn0TVNVfRXGN9SqrkEFujVsh_MuK06niXn93TuZixJu_eKRBwmW0-IwpdNaEUC33wBgozOXcjahhdWSVjL2kqJHxdWTt9sHXUofv3ddkbySNc8\" alt=\"Post-order Traversal to check for balanced binary tree\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First of all, we reached the leftmost node, <strong>Node 6: <\/strong>Left child = null so Left Height = 0, Right child = null so Right Height = 0, Difference is 0-0 = 0, ( 0 &lt;= 1 ) so return height, i.e. <strong>Max(0,0) + 1 = 1.&nbsp;<\/strong><\/li>\n\n\n\n<li><strong>Node 1:<\/strong> Left child = null so Left Height = 0, Right child = null so Right Height = 0, Difference is 0-0 = 0 , ( 0 &lt;= 1 ) so return height , i.e. <strong>Max(0,0) + 1 = 1.&nbsp;<\/strong><\/li>\n\n\n\n<li><strong>Node 0: <\/strong>Left child = null so Left Height = 0, Right child = null so Right Height = 0 , Difference is 0-0 = 0 , ( 0 &lt;= 1 ) so return height , i.e.<strong> Max(0,0) + 1 = 1.&nbsp;<\/strong><\/li>\n\n\n\n<li><strong>Node 7:<\/strong> Left child = 1 so Left Height = 1, Right child = 0 so Right Height = 1, Difference is 1-1= 0 , ( 0 &lt;= 1 ) so return height , i.e. <strong>Max(1,1) + 1 = 2.&nbsp;<\/strong><\/li>\n\n\n\n<li><strong>Node 3: <\/strong>Left child = 6 so Left Height = 1, Right child = 7 so Right Height = 2, Difference is 2-1= 1 , ( 1 &lt;= 1 ) so return height , i.e. <strong>Max(2,1) + 1 = 3 .&nbsp;<\/strong><\/li>\n<\/ul>\n\n\n\n<p>Now we know how to do it, let&#8217;s implement it in various programming languages.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the C++ program to check for balanced binary tree using post-order traversal:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\n\/\/ Definition for a binary tree node.\nstruct TreeNode {\n    int val;\n    TreeNode* left;\n    TreeNode* right;\n    TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n};\n\nclass Solution {\npublic:\n    \/\/ Function to check if the tree is balanced\n    bool isBalanced(TreeNode* root) {\n        \/\/ Call the helper function for DFS with post-order traversal\n        return dfsHeight(root) != -1;\n    }\n\n    \/\/ Helper function for DFS with post-order traversal to calculate tree height\n    int dfsHeight(TreeNode* root) {\n        \/\/ Base case: if the current node is NULL, return 0\n        if (root == NULL) return 0;\n\n        \/\/ Recursively calculate the height of the left subtree\n        int leftHeight = dfsHeight(root-&gt;left);\n        \/\/ If the left subtree is unbalanced, propagate -1 up the recursion\n        if (leftHeight == -1) \n            return -1;\n\n        \/\/ Recursively calculate the height of the right subtree\n        int rightHeight = dfsHeight(root-&gt;right);\n        \/\/ If the right subtree is unbalanced, propagate -1 up the recursion\n        if (rightHeight == -1) \n            return -1;\n\n        \/\/ Check if the current subtree is balanced\n        if (abs(leftHeight - rightHeight) &gt; 1)  \n            return -1;\n\n        \/\/ Return the height of the current subtree\n        return max(leftHeight, rightHeight) + 1;\n    }\n};\n\nint main() {\n    \/\/ Constructing the tree\n    TreeNode* root = new TreeNode(3);\n    root-&gt;left = new TreeNode(6);\n    root-&gt;right = new TreeNode(7);\n    root-&gt;right-&gt;left = new TreeNode(1);\n    root-&gt;right-&gt;right = new TreeNode(0);\n\n    \/\/ Creating an instance of the Solution class\n    Solution solution;\n\n    \/\/ Checking if the tree is balanced\n    bool balanced = solution.isBalanced(root);\n\n    \/\/ Output the result\n    if (balanced) {\n        cout &lt;&lt; &quot;The tree is balanced.&quot; &lt;&lt; endl;\n    } else {\n        cout &lt;&lt; &quot;The tree is not balanced.&quot; &lt;&lt; endl;\n    }\n\n    \/\/ Deallocating the memory\n    \/\/ In a complete program, you would want to free the allocated memory for the tree nodes\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Here is the Python program to check for a balanced binary tree:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\"># Definition for a binary tree node.\nclass TreeNode:\n    def __init__(self, x):\n        self.val = x\n        self.left = None\n        self.right = None\n\nclass Solution:\n    def isBalanced(self, root):\n        # Call the helper function for DFS with post-order traversal\n        return self.dfs_height(root) != -1\n\n    def dfs_height(self, root):\n        # Base case: if the current node is None, return 0\n        if root is None:\n            return 0\n\n        # Recursively calculate the height of the left subtree\n        left_height = self.dfs_height(root.left)\n        # If the left subtree is unbalanced, propagate -1 up the recursion\n        if left_height == -1:\n            return -1\n\n        # Recursively calculate the height of the right subtree\n        right_height = self.dfs_height(root.right)\n        # If the right subtree is unbalanced, propagate -1 up the recursion\n        if right_height == -1:\n            return -1\n\n        # Check if the current subtree is balanced\n        if abs(left_height - right_height) &gt; 1:\n            return -1\n\n        # Return the height of the current subtree\n        return max(left_height, right_height) + 1\n\n# Constructing the tree\nroot = TreeNode(3)\nroot.left = TreeNode(6)\nroot.right = TreeNode(7)\nroot.right.left = TreeNode(1)\nroot.right.right = TreeNode(0)\n\n# Creating an instance of the Solution class\nsolution = Solution()\n\n# Checking if the tree is balanced\nbalanced = solution.isBalanced(root)\n\n# Output the result\nif balanced:\n    print(&quot;The tree is balanced.&quot;)\nelse:\n    print(&quot;The tree is not balanced.&quot;)<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>You can implement it in Java also:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">\/\/ Definition for a binary tree node.\nclass TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n\n    TreeNode(int x) {\n        val = x;\n    }\n}\n\nclass Solution {\n    \/\/ Function to check if the tree is balanced\n    public boolean isBalanced(TreeNode root) {\n        \/\/ Call the helper function for DFS with post-order traversal\n        return dfsHeight(root) != -1;\n    }\n\n    \/\/ Helper function for DFS with post-order traversal to calculate tree height\n    private int dfsHeight(TreeNode root) {\n        \/\/ Base case: if the current node is null, return 0\n        if (root == null)\n            return 0;\n\n        \/\/ Recursively calculate the height of the left subtree\n        int leftHeight = dfsHeight(root.left);\n        \/\/ If the left subtree is unbalanced, propagate -1 up the recursion\n        if (leftHeight == -1)\n            return -1;\n\n        \/\/ Recursively calculate the height of the right subtree\n        int rightHeight = dfsHeight(root.right);\n        \/\/ If the right subtree is unbalanced, propagate -1 up the recursion\n        if (rightHeight == -1)\n            return -1;\n\n        \/\/ Check if the current subtree is balanced\n        if (Math.abs(leftHeight - rightHeight) &gt; 1)\n            return -1;\n\n        \/\/ Return the height of the current subtree\n        return Math.max(leftHeight, rightHeight) + 1;\n    }\n}\n\nclass Main {\n    public static void main(String[] args) {\n        \/\/ Constructing the tree\n        TreeNode root = new TreeNode(3);\n        root.left = new TreeNode(6);\n        root.right = new TreeNode(7);\n        root.right.left = new TreeNode(1);\n        root.right.right = new TreeNode(0);\n\n        \/\/ Creating an instance of the Solution class\n        Solution solution = new Solution();\n\n        \/\/ Checking if the tree is balanced\n        boolean balanced = solution.isBalanced(root);\n\n        \/\/ Output the result\n        if (balanced) {\n            System.out.println(&quot;The tree is balanced.&quot;);\n        } else {\n            System.out.println(&quot;The tree is not balanced.&quot;);\n        }\n\n        \/\/ In a complete program, you would want to free the allocated memory for the tree nodes\n    }\n}<\/pre><\/div>\n\n\n\n<p>The time complexity of the post-order traversal approach to check whether a binary tree is balanced or not is O(N), where N is the number of nodes in the binary tree. This is because each node is visited exactly once in a post-order traversal, and at each node, constant-time operations are performed.<\/p>\n\n\n\n<p>The Space Complexity of this approach is O(1) Extra Space + O(H) Recursion Stack space (H is the height of the binary tree).<\/p>\n\n\n\n<p>Before ending this article, let&#8217;s compare both the approaches:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular has-medium-font-size\"><table><thead><tr><th>Approach<\/th><th>Time complexity<\/th><th>Space complexity<\/th><th>Details<\/th><\/tr><\/thead><tbody><tr><td>Brute force approach<\/td><td>O(N*N)<\/td><td>O(1)\u00a0<\/td><td>Each node is visited multiple times to find the height of the left and right subtree for each node<\/td><\/tr><tr><td>Optimized approach<\/td><td>O(N)<\/td><td>O(1)\u00a0<\/td><td>Each node is visited exactly once in a post-order traversal, and at each node, constant-time operations are performed.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>By the way, there are many types of <a href=\"https:\/\/favtutor.com\/blogs\/tree-traversal-python-with-recursion\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/tree-traversal-python-with-recursion\">tree traversal<\/a> available in programming.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In this article, we have discussed two approaches for checking for a balanced binary tree, which is very popular in leetcode as well. We have used the optimized approach using post-order traversal to solve this problem and implemented its code in C++, Java, and Python.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand how to check for a balanced binary tree using post-order traversal approach and implement it in C++, Java, and Python.<\/p>\n","protected":false},"author":12,"featured_media":1180,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1178","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1178"}],"version-history":[{"count":5,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1178\/revisions"}],"predecessor-version":[{"id":1243,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1178\/revisions\/1243"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1180"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}