Check if binary tree is height balanced or not
Written by
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->left, result); int rh = checkBalanced(root->right, result); int currHeight = max(lh, rh) + 1; int leftRightSubtreeHeightDiff = abs(lh - rh); if(leftRightSubtreeHeightDiff > 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)