cbinary-treeavl-tree

LeetCode-1382. Balance a Binary Search Tree


struct TreeNodeC {
    int val;
    int height;
    struct TreeNodeC *left;
    struct TreeNodeC *right;
};

struct TreeNodeC *avl = NULL;

int check_balance_factor(struct TreeNodeC *root) {
    int balance_factor = 0;
    if (root->left == NULL && root->right == NULL) {
        balance_factor = 0;
    } else
    if (root->left == NULL && root->right != NULL) {
        balance_factor = (root->right)->height;
    } else
    if (root->left != NULL && root->right == NULL) {
        balance_factor = (root->left)->height;
    } else {
        balance_factor = ((root->left)->height) - ((root->right)->height);
        balance_factor = (balance_factor >= 0) ? (balance_factor) :(balance_factor * (-1));
    }
    return balance_factor;
}

struct TreeNodeC *heightImbalancingNode(struct TreeNodeC *root, bool *isFound) {
    struct TreeNodeC *TempB = NULL;
    if (root != NULL) {
        TempB = heightImbalancingNode(root->right, isFound);
        if ((*isFound) == false) {
            int bal_f = check_balance_factor(root);
            if (bal_f > 1) {
                *isFound = true;
                TempB = root;
                return TempB;
            }
        }
    }
    return TempB;
}

struct TreeNodeC *LLRotation(struct TreeNodeC *root, int val) {
    int val_temp = root->val;
    struct TreeNodeC *TempZ = (struct TreeNodeC *)malloc(sizeof(struct TreeNodeC));
    TempZ->val = root->val;
    TempZ->left = root->left;
    TempZ->right = root->right;
    TempZ->height = root->height;
    struct TreeNodeC *Temp = root->right;
    struct TreeNodeC *TempA = Temp->left;
    Temp->left = TempZ;
    (Temp->left)->right = TempA;
    if (val_temp == val) {
        avl = Temp;
    } else {
        *root = *Temp;
    }
    return Temp;
}

int maximum(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

int height(struct TreeNodeC *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + maximum(height(root->left), height(root->right));
}

int updateHeight(struct TreeNodeC **root) {
    if (*root == NULL) {
        return 0;
    }
    (*root)->height = height((*root));
    updateHeight(&((*root)->left));
    updateHeight(&((*root)->right));
    return 0;
}

struct TreeNodeC *createNode(int val) {
    struct TreeNodeC *newNode = (struct TreeNodeC *)malloc(sizeof(struct TreeNode));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->val = val;
    return newNode;
}

struct TreeNodeC *insertion(int val, struct TreeNodeC *root) {
    struct TreeNodeC *Temp = root;
    if (Temp == NULL) {
        struct TreeNodeC *newNode = createNode(val);
        return newNode;
    }
    while (1) {
        if (val < Temp->val) {
            if (Temp->left == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->left = newNode;
                return root;
            }
            Temp = Temp->left;
        } else {
            if (Temp->right == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->right = newNode;
                return root;
            }
            Temp = Temp->right;
        }
    }
}

struct TreeNodeC *avlTreeInsertion(int val) {
    bool isFound = false;
    avl = insertion(val, avl);
    updateHeight(&avl);
    struct TreeNodeC *ll = heightImbalancingNode(avl, &isFound);
    if (isFound) {
        struct TreeNodeC *rotated = LLRotation(ll, avl->val);
        return avl;
    }
    return avl;
}

void inOrderTraversal(struct TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        avlTreeInsertion(root->val);
        inOrderTraversal(root->right);
    }
}
struct TreeNodeC *balanceBST(struct TreeNode *root) {
    inOrderTraversal(root);
    return avl;
}

I have written this code to height balance a binary search Tree. This solution is working fine. In leet code I am getting Time limit Exceeded for larger inputs. Can someone one help me where can I make this better to beat the TLE error. Please don't post a whole new solution to solve this problem. I want the problem to be solved in the approach which I took but with better time complexity


Solution

  • 
     
    struct TreeNodeC* balanceBST(struct TreeNode* root){    
        struct TreeNodeC
    {
         int val;
         int height;
         struct TreeNodeC *left;
         struct TreeNodeC *right;
     };
        struct TreeNodeC* avl=NULL;
        int check_balance_factor(struct TreeNodeC * root)
    {
        int balance_factor = 0;
        if(root->left==NULL && root->right==NULL)
        {
            balance_factor = 0;
        }
        else if(root->left==NULL && root->right!=NULL)
        {
            balance_factor =  (root->right)->height;
        }
        else if(root->left!=NULL && root->right==NULL)
        {
            balance_factor = (root->left)->height;
        }
        else
        {
            balance_factor =((root->left)->height) - ((root->right)->height);
            balance_factor=(balance_factor>=0)?(balance_factor):(balance_factor*(-1));
        }
        return balance_factor;
    }   
    struct TreeNodeC* heightImbalancingNode(struct TreeNodeC* root,bool* isFound)
    {
              struct TreeNodeC* Temp=NULL; 
            if(root!=NULL)
            {    
                Temp= heightImbalancingNode(root->right,isFound);
                if((*isFound)==false)
                {
                int bal_f=check_balance_factor(root); 
                    if(bal_f>1)
                    {
                    *isFound=true;
                    Temp=root;
                    return Temp;
                    }
                }
            }
            return Temp;      
    }
        void LLRotation(struct TreeNodeC* root,int val){
            int val_temp=root->val;
            struct TreeNodeC* TempZ=(struct TreeNodeC* )malloc(sizeof(struct TreeNodeC));
            TempZ->val=root->val;
            TempZ->left=root->left;
            TempZ->right=root->right;
            TempZ->height=root->height;
            struct TreeNodeC* Temp=root->right;
            struct TreeNodeC* TempA=Temp->left;
            Temp->left=TempZ;
            (Temp->left)->right=TempA; 
            if(val_temp==val){
               avl=Temp; 
            }
            else{
                *root=*Temp;
            }    
    }
        int maximum(int a,int b)
        {
            if(a>b){
                return a;
            }
            return b;
        }
        int updateHeight(struct TreeNodeC* root)
        {
            if(root==NULL)
            {
                return 0;
            }
            root->height= 1+maximum(updateHeight(root->left),updateHeight(root->right));
            return root->height;
           
        }
        struct TreeNodeC* createNode(int val)
        {
            struct TreeNodeC* newNode=(struct TreeNodeC*) malloc(sizeof(struct TreeNode));
            newNode->left=NULL;
            newNode->right=NULL;
            newNode->val=val;
            return newNode;
        }
       
         struct TreeNodeC* insertion(int val,struct TreeNodeC* root)
         {
           struct TreeNodeC* Temp=root; 
            if(Temp==NULL){
                struct TreeNodeC* newNode=createNode(val);
                return newNode;    
        }
           while(1)
           {
               if(val<Temp->val)
               { 
                   if(Temp->left==NULL)
                   {
                       struct TreeNodeC* newNode=createNode(val);
                       Temp->left=newNode;
                       return root;
                   }
                   Temp=Temp->left;
               }
               else{
                  
                   if(Temp->right==NULL){
                       struct TreeNodeC* newNode=createNode(val);
                       Temp->right=newNode;
                       return root;
                   }
                    Temp=Temp->right;
               }
           }
        }
       void avlTreeInsertion(int val)
       {
           bool isFound=false;
           avl= insertion(val,avl);
            updateHeight(avl);
           struct TreeNodeC* ll= heightImbalancingNode(avl,&isFound);
           if(isFound){
            LLRotation(ll,avl->val);
           }
       }
      void inOrderTraversal(struct TreeNode* root){
          if(root!=NULL){
          inOrderTraversal(root->left);  
          avlTreeInsertion(root->val);
          inOrderTraversal(root->right);
          }   
      }    
       inOrderTraversal(root);
        return avl;      
    }
    

    Made some small changes in the program. It is working now