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