Recent Posts

Check if binary tree is height balanced or not

Written by

studymite

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 lh = checkBalanced(root-&gt;left, result);
int rh = checkBalanced(root-&gt;right, result);

int currHeight = max(lh, rh) + 1;
int leftRightSubtreeHeightDiff = abs(lh - rh);

if(leftRightSubtreeHeightDiff &gt; 1) result = false;

if(!result) return 0;

return currHeight;



}


int main() {
/*
1
/    

2      3
/   \   /  

4     5 6    7
/
struct Node 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)

Check if binary tree is height balanced or not