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