{"post":"

Problem

A binary tree in which the left and right subtrees of every node differ in height by no more than 1 is called a height-balanced binary tree. Check if the given tree is height-balanced or not.

Brute Force Approach

We calculate the height at every node and check if the tree is height-balanced or not.

TC – O(N²)

Better Approach

We will keep track left and right height of the subtree in a variable at each node and if at any node the absolute difference of left and right height is greater than 1 we’ll return false.

#include<bits/stdc++.h>\r\nusing namespace std;\nstruct Node{\r\nint data;\r\nNode* left;\r\nNode* right;\r\nNode(int data){\r\nthis->data = data;\r\nleft = right = NULL;\r\n}\r\n};
\nint checkBalanced(Node* root, bool &result){\r\nif(!root) return 0;
\nint lh = checkBalanced(root-&gt;left, result);\r\nint rh = checkBalanced(root-&gt;right, result);\r\n\r\nint currHeight = max(lh, rh) + 1;\r\nint leftRightSubtreeHeightDiff = abs(lh - rh);\r\n\r\nif(leftRightSubtreeHeightDiff &gt; 1) result = false;\r\n\r\nif(!result) return 0;\r\n\r\nreturn currHeight;\n
\n}
\nint main() {\r\n/*\r\n1\r\n/    
\n2      3\r\n/   \\   /  
\n4     5 6    7\r\n/\r\nstruct Node root = new Node(1);\r\nroot->left = new Node(2);\r\nroot->left->left = new Node(4);\r\nroot->left->right = new Node(5);\r\nroot->right = new Node(3);\r\nroot->right->left = new Node(6);\r\nroot->right->right = new Node(7);\r\nbool result = true;\r\ncheckBalanced(root, result);\r\ncout<<result;\r\nreturn 0;\r\n}

TC – O(N)

\n","title":"Check if binary tree is height balanced or not","authorDetails":{"name":"studymite","slug":"admin"},"description":"We'll check if the given tree is height balanced or not using brute force approach first and then move towards the optimal solution.","slug":"check-if-binary-tree-is-height-balanced-or-not/","articleId":"636a83417bb1ce5072622aff","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}