Insert and delete item in a BST

 #include <stdio.h>

#include <stdlib.h>
struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
};
int arr[9], i = 0;
struct tree *Createnode(int data)
{
    struct tree *nd = (struct tree *)malloc(sizeof(struct tree));
    nd->left = NULL;
    nd->right = NULL;
    nd->data = data;
    return nd;
}
void inOrderTraversal(struct tree *root)
{
    if (root != NULL)
    {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        arr[i++] = root->data;
        inOrderTraversal(root->right);
    }
}

void preOrderTraversal(struct tree *root)
{
    if (root != NULL)
    {
        printf("%d ", root->data);
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}
struct tree *Least_rst(struct tree *root)
{
    struct tree *temp = root->right;
    if (temp == NULL)
    {
        printf("No element in Right sub tree\n");
        return root;
    }
    else
    {
        while (temp->left)
        {
            temp = temp->left;
        }
        return temp;
    }
}
struct tree *Max_lst(struct tree *root)
{
    struct tree *temp = root->left;
    if (temp == NULL)
    {
        printf("No element in Right sub tree\n");
        return root;
    }
    else
    {
        while (temp->right)
        {
            temp = temp->right;
        }
        return temp;
    }
}
struct tree* insertElement(struct tree *root, int item)
{
    struct tree *temp = root;
    struct tree *node = Createnode(item);
    if (temp == NULL)
    {
        

        // struct tree *root = Createnode(item);
        struct tree *n1 = Createnode(item);
        return n1;
    }
    else
    {
        while (temp)
        {
            if (temp->data == node->data)
            {
                printf("Insertion not possible since tree already contains element %d.\n", item);
                break;
            }

            else if (node->data < temp->data)
            {
                if (temp->left == NULL)
                {

                    temp->left = node;
                    break;
                }
                else
                    temp = temp->left;
            }
            else if (node->data > temp->data)
            {
                if (temp->right == NULL)
                {

                    temp->right = node;
                    break;
                }
                else
                    temp = temp->right;
            }
        }
        return root;
    }
}
struct tree *deletenode(struct tree *root, int value)
{
    struct tree *temp = root;

    if (temp == NULL)
    {
        printf("No such element found in the Binary tree : %d\n\t OR\nThe Tree is Empty\n", value);
        return root;
    }
    else
    {
        if (temp->data > value)
            temp->left = deletenode(temp->left, value);

        else if (temp->data < value)
            temp->right = deletenode(temp->right, value);

        else
        {
            if (!temp->left && !temp->right)
            {
                struct tree *temp1 = NULL;
                free(temp);
                return temp1;
            }
            else if (temp->left && temp->right)
            {
                struct tree *temp1 = Least_rst(temp);
                temp->data = temp1->data;
                temp->right = deletenode(temp->right, temp1->data);
            }
            else
            {
                if (temp->left == NULL)
                {
                    struct tree *temp2 = temp->right;
                    free(temp);
                    return temp2;
                }
                else 
                {
                    struct tree *temp2 = temp->left;
                    free(temp);
                    return temp2;
                }
            }
        }
    }
}

int main()
{
    struct tree *t = Createnode(9);
    struct tree *t1 = Createnode(4);
    struct tree *t2 = Createnode(11);
    struct tree *t4 = Createnode(2);
    struct tree *t5 = Createnode(6);
    struct tree *t6 = Createnode(15);
    struct tree *t7 = Createnode(5);
    struct tree *t8 = Createnode(8);
    struct tree *t9 = Createnode(12);

    t->left = t1;
    t->right = t2;
    t1->left = t4;
    t1->right = t5;
    t5->right = t8;
    t5->left = t7;
    t2->right = t6;
    t6->left = t9;
    
    t  = insertElement(t , 25);
    t  = insertElement(t , 3);
    t  = insertElement(t , 7);
    t  = insertElement(t , 9);
    t = deletenode(t , 15);
    preOrderTraversal(t);
    printf("\n");
    inOrderTraversal(t);
    printf("\n");

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Height of the Tree.

  Below is the source code of checking the height of the binary tree. If you need any explanation then please feel free to contact me on my email i.e harshprasadaju@gmail.com. Thankyou. #include   <stdio.h> #include   <stdlib.h> struct   tree {      int   data ;      struct   tree   * left ;      struct   tree   * right ; }; struct   tree   * Createnode ( int   data ) {      struct   tree   * nd   =  ( struct   tree   * ) malloc ( sizeof ( struct   tree ));      nd -> left   =   NULL ;      nd -> right   =   NULL ;      nd -> data   =   data ;      return   nd ; } void   inOrderTraversal ( struct   tree   * root ) {      if  ( root   != ...
Read more

Multiple parenthesis balancing problem using stacks

  Below is the source code of parenthesis balancing problem using stacks. If you need any explanation then please feel free to contact me on my email i.e harshprasadaju@gmail.com. Thankyou. #include   <stdio.h> //Ignore spellings error #include   <stdlib.h> #include   <string.h> struct   stack {      int   top ;      int   size ;      char   * arr ; }; int   isEmpty ( struct   stack   * ptr ) {      if  ( ptr -> top   ==   - 1 )          return   1 ;      return   0 ; } struct   stack   * createStack ( int   size ) {      struct   stack   * s   =  ( struct   stack   * ) malloc ( sizeof ( struct   stack ));      s -> size   =   size ;   ...
Read more