TutorialStudyMite
Check if binary tree is height balanced or not
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
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(N2)
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>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
int checkBalanced(Node* root, bool &result){
if(!root) return 0;
}
int main() {
/*
1
/
2 3
/ \ /
4 5 6 7
root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
bool result = true;
checkBalanced(root, result);
cout<<result;
return 0;
}TC – O(N)
Finished reading?