jain12

How to determine if a binary tree is height-balanced (2)

Mar 13th, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 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 IsBalanced(Node *root,int &height){
  15.  int lh=0,rh=0;
  16.  if(root==NULL){
  17.     height=0;
  18.     return 1;
  19.     }
  20.  int l=IsBalanced(root->left,lh);
  21.  int r=IsBalanced(root->right,rh);
  22.  height=max(lh,rh)+1;
  23.  if(abs(lh-rh)>=2)
  24.    return 0;
  25.  return l && r;
  26.  }
  27.  
  28. void Insert(Node **root_ref,int key){
  29.   if(*root_ref==NULL){
  30.     *root_ref=new Node(key);
  31.     return;
  32.     }
  33.   if((*root_ref)->data<key)
  34.     Insert(&((*root_ref)->right),key);
  35.   else
  36.      if((*root_ref)->data>key)
  37.        Insert(&((*root_ref)->left),key);
  38.   }
  39.  
  40. int main(){
  41.  Node *root=NULL;
  42.  Insert(&root,5);
  43.  Insert(&root,7);
  44.  Insert(&root,6);
  45.  Insert(&root,2);
  46.  Insert(&root,8);
  47.  int height=0;
  48.  if(IsBalanced(root,height))
  49.    cout<<"yes";
  50.  else
  51.    cout<<"no";
  52.  }
Add Comment
Please, Sign In to add comment