jain12

How to determine if a binary tree is height-balanced

Mar 13th, 2020
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include<cstdlib>
  2. #include<iostream>
  3. using namespace std;
  4. class Node{
  5.   public:
  6.       int data;
  7.       Node *left,*right;
  8.       Node(int key){
  9.         data=key;
  10.         left=right=NULL;
  11.         }
  12.   };
  13.  
  14.   int Height(Node* root){
  15.     if(root==NULL)
  16.       return 0;
  17.     return max(Height(root->left),Height(root->right))+1;
  18.     }
  19.  
  20.  int CheckHeightBalanced(Node *root){
  21.   if(root==NULL)
  22.      return 1;
  23.   int height_diffrence=abs(Height(root->left)-Height(root->right));
  24.  return (CheckHeightBalanced(root->left)&&CheckHeightBalanced(root->right)&&height_diffrence<=1);
  25.   }
  26.  
  27. void Insert(Node **root_ref,int key){
  28.   if(*root_ref==NULL){
  29.     *root_ref=new Node(key);
  30.     return;
  31.     }
  32.   if((*root_ref)->data<key)
  33.     Insert(&((*root_ref)->right),key);
  34.   else
  35.      if((*root_ref)->data>key)
  36.        Insert(&((*root_ref)->left),key);
  37.   }
  38.  
  39. int main(){
  40.  Node *root=NULL;
  41.  Insert(&root,5);
  42.  Insert(&root,7);
  43.  Insert(&root,6);
  44.  Insert(&root,2);
  45.  Insert(&root,8);
  46.  if(CheckHeightBalanced(root))
  47.    cout<<"yes";
  48.  else
  49.    cout<<"no";
  50.  }
Add Comment
Please, Sign In to add comment