BST with parent node (using recursion)

We can also introduce new pointer to the every node i.e. parent node which will store the pointer to the parent node of that node. The parent of root node is null so the parent pointer of root node will point to null in that case and root node is the only node whose pointer is NULL. 
the program is 

#include<stdio.h>

struct node
{
    int key ;
    struct node *parent;
    struct node *left;
    struct node *right;
};
struct node *prev_node=NULL;
typedef struct node* NODE;
void main ()
{
    NODE root = NULL;
    insertion(&root,40);
    insertion(&root,25);
    insertion(&root,70);
    insertion(&root,22);
    insertion(&root,35);
    insertion(&root,60);
    insertion(&root,80);
    insertion(&root,90);
    insertion(&root,10);
    insertion(&root,30);
    deletion(&root,45);
    inorder(root);

}
void insertion(NODE* m,int value)
{
    NODE current= *m;
    NODE temp = (NODE)malloc(sizeof(struct node));
    temp->key= value ;
      temp->left=NULL;
    temp->right=NULL;
     prev_node=current ;
    if (current== NULL)
    {
        *m= temp;
        temp->parent = prev_node;
    }

    else if(current->key > value )
    {
        insertion(&current->left,value);

    }
    else if(current->key <value)
    {
        insertion(&current->right,value);
    }

}

void deletion(NODE **m,int value)
{


    NODE current= *m;
    if (current==NULL)
    {
        printf ("node doesn't exit");
        return;
    }
    if (current->key>value )
    {
          deletion(&current->left,value);

    }
    else if(current->key <value)
    {
        deletion(&current->right,value);
    }

    else
    {
        if((current->left==NULL)&&(current->right==NULL))
        {
            *m==NULL;
            current->parent=NULL;
        }
        else if(current->right==NULL)
        {
            *m=current->left;
            current->left->parent=current->parent;
            current->parent=NULL;    /*optional*/

        }
        else if(current->left==NULL)
        {
            *m= current->right;
            current->right->parent=current->parent;
            current->parent=NULL;
        }
        else
        {
            int next_big = successor(current);
            current->key = next_big;
            deletion(&current->right,next_big); /*that deletion will not recurse as it will terminate in case 1 and 2 above as successor will either be leave node or node with one child */

        }


    }



}

int successor(NODE m )
{
     NODE x= m->right;
    if (x->left!=NULL )
    {
        x=x->left;
    }
    return x;

}

void inorder(NODE m )
{
    if (m==NULL)
    return ;
    else
    {
        inorder(m->left);
        printf("%d\n",m->key);
        inorder(m->right);
    }



}

BST program ( Binary Search Tree) creation / insertion/ deletion/preorder travesal C program

today we will be discussing about very important trees that is binary search trees. Here the parent node is smaller than the right child and greater than the left child. and left and right children are also a binary tree . 
if we want to add the elements in binary search tree we have to maintain the BST property see the program and you will understand about this . 

#include<stdio.h>
struct node
{
    int key ;
    struct node *left;
    struct node *right;
};
typedef struct node* NODE;
void main ()
{
    NODE root = NULL;
    insertion(&root,40);
    insertion(&root,25);
    insertion(&root,70);
    insertion(&root,22);
    insertion(&root,35);
    insertion(&root,60);
    insertion(&root,80);
    insertion(&root,90);
    insertion(&root,10);
    insertion(&root,30);
    deletion(&root,45);
    inorder(root);

}
void insertion(NODE* m,int value)
{
    NODE current= *m;
    NODE temp = (NODE)malloc(sizeof(struct node));
    temp->key= value ;
      temp->left=NULL;
    temp->right=NULL;
    if (current== NULL) /* if the root is node is already empty */
    {
        *m= temp;
    }
    else if(current->key > value ) /* we will try to find the exact position by comparing keys */
    {
        insertion(&current->left,value);

    }
    else if(current->key <value)
    {
        insertion(&current->right,value);
    }

}

void deletion(NODE **m,int value)
{


    NODE current= *m;
    if (current==NULL)       /* if current node is NULL it means that node doesn't exit because null is                                                last node in a tree */
    {
        printf ("node doesn't exit");
        return;
    }
    if (current->key > value ) /*we will try to find the exact location where the node we are deleting                                                    will lie */
    {
          deletion(&current->left,value);

    }
    else if(current->key <value)
    {
        deletion(&current->right,value);
    }

    else       /* we are on the node where key == value we are deleting it can have four cases */
    {
        if((current->left==NULL)&&(current->right==NULL)) /*1> both children are null */
        {
            *m==NULL;
        }
        else if(current->right==NULL) /* 2>only right child is null but on left there is a valid child */
        {
            *m=current->left;

        }
        else if(current->left==NULL) /*3>only left child is null but on right there is a valid child */
        {
            *m= current->right;
        }
        else       /* both children exist */
        {
            int next_big = successor(current); /* try to find the next element */
            current->key = next_big;    
            deletion(&current->right,next_big);  /*delete the node successor from there */

        }


    }



}

int successor(NODE m )
{
     NODE x= m->right;
    if (x->left!=NULL )
    {
        x=x->left;
    }
    return x;

}

void inorder(NODE m )
{
    if (m==NULL)
    return ;
    else
    {
        inorder(m->left);
        printf("%d\n",m->key);
        inorder(m->right);
    }



}

Counting sort / Linear sort

Till now we discussed about sorting which are comparison based and they were taking at-least nlogn time. Here i am discussing a new sorting algorithm that will sort the numbers in linear time but nothing comes free so same case applies here. Counting sort sort the element in linear time but uses lot of your (computer) space  while performing sorting. 

and it creates a array C where it will store the numbers of elements corresponding to indexes and in array B we will be getting the sorted element. 

so here is the program 

#include<stdio.h>

int size;

void main()

{

    int A[]={2,5,4,1,6,5,3,9,6,4,8};

    size=sizeof A/sizeof A[0];

    counting_sort(A);

}

void counting_sort(int *A)

{

    int key = finding_maximum(A);

    int B[size];

    int C[key+1],i;

    for (i=0;i<=key;i++)

    {

        C[i]=0;   /*making all elements of C  zero */

    }

    for(i=0;i<size;i++)

    {

        C[A[i]]=C[A[i]]+1; /*increasing the frequencies of every key(i.e. index of array C)  according to                                            elements in array A*/

    }

    for(i=1;i<=key;i++)

    {

        C[i]=C[i]+C[i-1];   /*adding the frequencies to make it cumulative frequencies in array C */

    }

    for(i=0;i<size;i++)

    {

       B[C[A[i]]-1]=A[i]; /*storing the elements in array B according to the position given in array C */

        C[A[i]]--;

    }

    output(B);

}

int finding_maximum(int *A)

{

    int max =A[0],i;

    for(i=1;i<=size;i++)

    {

        if (A[i]>max)

        {

            max=A[i];

        }

    }

    return max;

}

void output(int *A)

{

    int i;

    for(i=0;i<size;i++)

    {

        printf("%d\n",A[i]);

    }

}

Heap sort

Today we will be discussing about Heap sort. This sorting first tries to build a max heap and once you get a max heap . you can easily sort the element by swapping the maximum element with last element. you can read the theory from standard book "clrs" or  Wikipedia if you don't know what is max heap

Here is the program for heap sort. i am using three functions first one is heapsort which will sort the elements once you get max heap in order to build max heap i am calling a function called building_max_heap which will max_heapify function to build a max heap for random numbers 

#include<stdio.h>
int heap_size;
void main()
{
    int A[]={23,65,2,6,12,43,76,845,93,86};
    heap_size=sizeof A/sizeof A[0];
    heap_sort(A);
}

void heap_sort(int *A)
{
    int n ;
    building_max_heap(A);
    for(n=heap_size-1;n>=0;n--)
    {
        printf("%d\n",A[0]);
        swap(&A[n],&A[0]);
        heap_size= heap_size-1;
        max_heapify(A,0);
    }

}

void building_max_heap(int *A)       /* this function will create a max heap on random array by using                                                                max_heapify function */
{
    int i,n = heap_size-1;        /*heap size is the last index +1 as index is starting from 0 */
    for(i=(n-1)/2;i>=0;i--)       /*as internal nodes will start from (n-1)/2 in almost complete binary tree                                                   and the leaves are already in heap */
    {
        max_heapify(A,i);
    }

}

void max_heapify(int *A,int i)   /*this function will assume that left and right children of i are already                                                       in heap now we want to add the i^th element( i.e. root) in heap */  

{
    int left = 2*i+1;
    int right= 2*i+2;
    int max;
    if(A[left]>A[i]&&left<=heap_size-1)
    {
        max = left;
    }
    else max= i ;
    if(A[right]>A[max]&&right<=heap_size-1)
    {
        max= right;
    }
    if (max!=i)
    {
        swap(&A[i],&A[max]);
        max_heapify(A,max);
    }

}


void swap(int *m, int *n)
{
    int temp = *m;
    *m=*n;
    *n=temp;
}

Linked list Insertion / Creating linked list

Today we are starting linked . and the simplest program of linked is inserting element in a linked list . there can be various insertion elements anywhere in linked list and can also create new one . i am discussing three methods 
1> if you want to add element at end of linked list 
2> you wanted to add the element at first position means opposite to first one . 
3> suppose you are giving the pointer of previous node where you want to insert element 

for this i used three different functions respectively 
1> append ()
2> push()
3> insert_after()

#include<stdio.h>
struct node
{
    int data;
    struct node* next;
};

void main()
{
    struct node* head = NULL;
    append(&head,7); /*append is a function that will add the node at end */
    append(&head,6);
    push(&head,9);  /*push will add the element on head */
    insert_after(head->next->next, 43);
    push(&head, 64);
    output(head);
}

void append(struct node** m, int value) /*  m is a pointer that is storing the address of head  */
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data=value;
    temp->next= NULL;
    struct node *current = *m ; /*  (*m) means that value at the head as m was storing the address of head )*/
       /*current has same value now that of head */
    if(*m == NULL)
    {
        *m = temp;
    }

    else
    {
        while(current ->next!= NULL)
        {
            current=current->next;
        }
        current->next=temp;
    }
}

 void push(struct node **m , int value )
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data=value;
    temp->next = *m; /* (*m) means that value at the head as m was storing the address of head )*/
    *m= temp; /*head will change by this */

}

void insert_after(struct node *prev_node,int value)
{
    if (prev_node== NULL)
    {
        printf("previous node can't be null");
        return;
    }
    else
    {
        struct node* temp = (struct node*)malloc(sizeof(struct node));
        temp->data=value;
        temp->next      =    prev_node->next ;
        prev_node->next =    temp;

    }

}

void output(struct node* current)
{
    while(current!=NULL)
    {
        printf("%d\n",current->data);
        current=current->next;
    }

}

the following picture will explain the pointers used in append function 

and this picture will explain the insert_after function