Check if a given Binary Tree is height balanced like a Red | Program to check if a given Binary Tree is balanced like a Red - Black Tree ; utility that allocates a new Node with the given key ; Returns returns tree if the Binary tree is balanced like a Red - Black tree . This function also sets value in maxh and minh ( passed byreference ) . maxh and minh are set as maximum and minimum heights of root . ; Base case ; To store max and min heights of left subtree ; To store max and min heights of right subtree ; Check if left subtree is balanced , also set lmxh and lmnh ; Check if right subtree is balanced , also set rmxh and rmnh ; Set the max and min heights of this node for the parent call ; See if this node is balanced ; A wrapper over isBalancedUtil ( ) ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; Node * left , * right ; } ; Node * newNode ( int key ) { Node * node = new Node ; node -> key = key ; node -> left = node -> right = NULL ; return ( node ) ; } bool isBalancedUtil ( Node * root , int & maxh , int & minh ) { if ( root == NULL ) { maxh = minh = 0 ; return true ; } int lmxh , lmnh ; int rmxh , rmnh ; if ( isBalancedUtil ( root -> left , lmxh , lmnh ) == false ) return false ; if ( isBalancedUtil ( root -> right , rmxh , rmnh ) == false ) return false ; maxh = max ( lmxh , rmxh ) + 1 ; minh = min ( lmnh , rmnh ) + 1 ; if ( maxh <= 2 * minh ) return true ; return false ; } bool isBalanced ( Node * root ) { int maxh , minh ; return isBalancedUtil ( root , maxh , minh ) ; } int main ( ) { Node * root = newNode ( 10 ) ; root -> left = newNode ( 5 ) ; root -> right = newNode ( 100 ) ; root -> right -> left = newNode ( 50 ) ; root -> right -> right = newNode ( 150 ) ; root -> right -> left -> left = newNode ( 40 ) ; isBalanced ( root ) ? cout << " Balanced " : cout << " Not ▁ Balanced " ; return 0 ; }