Ticker

6/recent/ticker-posts

Header Ads Widget

Responsive Advertisement

Check for Balanced Tree || 3 approach



/**
    int height(struct Node* node){
    
    if(node==NULL)
    {
        return 0;
    }
    int leftt=height(node->left);
    int rightt=height(node->right);
    return 1+max(leftt,rightt);
    }
    bool isBalanced(Node *root)
    {
        if(root==NULL)
        {
            return true;
        }
         return (abs((height(root->left))-height(root->right))<=1) && isBalanced(root->left) && 
         isBalanced(root->right);
    }
    
    */
    
// Another Approach
/**
    bool isBalanced(Node *root)
    {
            if(height(root)==-1) return false;
            return true;
    }
    int height(struct Node* node)
    {
        
        if(node==NULL)
        {
            return 0;
        }
        int lh=height(node->left);
        int rh=height(node->right);
        if(lh==-1|| rh==-1)
        {
            return -1;
        }
        if(abs(lh-rh)>1) {
            return -1;
        }
        return 1+max(lh,rh);
    }**/
    
    
// 3rd Approach
 int height(struct Node* node){
    
    if(node==NULL)
    {
        return 0;
    }
    int leftt=height(node->left);
    int rightt=height(node->right);
    return 1+max(leftt,rightt);
    }
    bool isBalanced(Node *root)
    {
          if(root==NULL)
          {
              return true;
          }
          if(isBalanced(root->left)==false)
          {
              return false;
          }
          if(isBalanced(root->right)==false)
          {
              return false;
          }
          int lh=height(root->left);
          int rh=height(root->right);
          if(abs(lh-rh)<=1)
          {
              return true;
          }
          else{
               return false;
          }
         
    }

Post a Comment

0 Comments