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 

Quick sort

Quick sorting is an important algorithm as it uses divide and conquer approach and here in this algorithm we divide the array into two arrays where in one array all elements smaller than pivot will be stored and in second all the elements greater than pivot will store. 
After getting two arrays we will again apply the same procedure and in last we will be getting the sorted array 

the idea is this 
and the program is 

#include<stdio.h>
#define first 0
void main()
{
    int A[]={23,6,5,17,54,2,4,9,76,24,84,286};
    int size= sizeof A/sizeof A[0];
    quick_sort(A,first,size-1);
    output(A,size);

}
void quick_sort(int *A,int p,int r)
{
    if(p<r)
    {
        int pivot=A[r];
        int i=p-1,j;
        for(j=p;j<r;j++)
        {
            if(A[j]<pivot)
            {
            i++;
            swap(&A[i],&A[j]);
            }
        }
        A[r]=A[i+1];    /*change the pivot position to its original position where the boundary between                                         two arrays(smaller than pivot and larger than pivot) will exist*/
        A[i+1]=pivot;
        quick_sort(A,p,i); 
                                 /* as the pivot element that we choose is now on i+1 position see above line */
        quick_sort(A,i+2,r);  
                          /*we are not  passing the pivot(i.e. i+1position) as it is already on its right position*/
    }
}

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

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

Bubble Sort

Today we will be discussing about bubble sort . In this sorting the biggest bubble(ie maximum number) will go on the end position after first iteration . 
Then we will move the second largest bubble(ie second largest number) on the second last  position.
and so on . 
So the simple program for bubble sort is 

 #include<stdio.h>
void main()
{
    int A[]={23,76,4,12,76,32,98,54,13,65};
    int size = sizeof A/sizeof A[0];
    bubble_sort(A,size);
    output(A,size);
}

void bubble_sort(int *A,int size)
{
    int i,j;
    for(i=0;i<size-1;i++)
    {
        for(j=0;j<size-i-1;j++)
        {
            if(A[j]>A[j+1])
            {
                swap(&A[j],&A[j+1]); /* swap the number if first number is larger as we are trying to                                                                             move the larger number in end */
            }
        }
    }
}
void swap(int *m, int *n)
{
    int temp = *m;
    *m=*n;
    *n=temp;
}

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

Selection sort

Now today i will be discussing about selection sort too . in this sorting we first try to find the maximum element and then we place it in array's first position . 

After this step we find second greatest element and place it in second position of array and so on. 

So the simple program for selection sort is

 #include<stdio.h>

void main()

{

    int array1[]={32,67,8,54,21,43,76,83,12,32},i;

    selection(array1,9);

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

    {

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

    }

}

void selection(int *A,int n )

{

    int i,j,temp;

    for(i=0;i<=n-1;i++)

    {

        for (j=i;j<=n;j++)

        {

            if (A[i]>A[j])

                                     /*checking if the element that we are comparing is smaller than our assumption of minimum change it */

            {

                temp = A[j];

                A[j]=A[i];

                A[i]=temp;

            }

        }

    }

}

Insertion sorting

Today we will be talking abut insertion sort . This is a very simple program but an important algorithm for sorting the numbers . The approach is quite similar to sorting of playing cards . when we find a new number we will move that card there and will shift the other cards.
here is the program

       #include<stdio.h>
void main()
{
    int A[]= {12,65,32,87,98,21,43,14,65,76};
    int size= sizeof(A)/ sizeof(A[0]) ;        /*it will give number of elements*/
    insertion_sort(A,size);
    output(A,size);

}
void insertion_sort(int *A,int size)
{
    int i ,j;
    for (i=1;i<size;i++)                   /*as last index=size-1*/
    {
        int key =A[i];
        j=i-1;
        while (A[j]>key&&j>0)      /* loop will go on and on & swaps until A[j] is smaller than key */
        {
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=key;
    }
}

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

program explaining merge sort without saving the random number in left and right array

lot of people are finding difficulty in left[i]= 10000 so here's the solution 
well in my previous blog yesterday the approach that i followed was similar to cormen where they initialize the the next  element after filling the let and right sub array as ∞ which means the element should be higher than all the elements present for sorting but that may not be the case .. as you will never know what a person can enter . 
here some people will say that we can enter the largest that is available for that language for example for c it signed 32467 ( for 32 bit compiler ) and it can also vary from system to system so you can  use this approach 
#include<stdio.h>
#include<conio.h>
void main()
{
     int i,array1[]={1,5,7,84,32,76,41,62,79,13};
     merge(array1,0,9);
    for( i=0;i<=9;i++)
    {
          printf("%d\n",array1[i]);
    }
}

void merge(int *A,int p,int n)
{
  if (p==n)
    {
    return;
    }
  else
   {

    int q=p+(n-p)/2;
    printf("now calling merge(A,%d,%d)\n",p,q);
    merge(A,p,q);
    printf(" now calling merge(A,%d,%d)\n",q+1,n);
    merge(A,q+1,n);
    printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
    combine(A,p,q,n);
   }
}
void combine(int *A,int p,int x,int n)
{
    int i = 0;
    int j=0;
    int n1 = p ;
    int n2 = x;
    int left[10];
    int right[10];
    for( i=0;p<=x;i++,p++)
    {
            left[i] = A[p];
            printf("the element added in left now which is %d",left[i]);

    }


    for(i=0;(x+1)<=n;x++,i++)
    {
        right[i] = A[x+1];
        printf("the element added in right now which is  %d",right[i]);

    }
    printf("\n");
    p=n1; /*now p contains the starting value as we modified the value in first loop */
    for(i=0,j=0;(i<n2-n1+1)&&(j<n-n2);p++) /* as (n2-n1+1) would be giving the number of elements in left array but here in left array we are starting from 0 that's why we didn't use equal to sign*/
    {
        if((i!=n2-n1+1)&&(left[i]<right[j]))
        {
            A[p]=left[i];
            printf("the element added in A[%d] which is %d \n",n1,A[p]);
            i++;
        }
        else
        {

            A[p]= right[j];
            printf("the element added from right \n",A[p]);
            j++;
        }
    }
    if(i == n2-n1+1 ) /*means all the elements of the left array are copied but there can be elements in right */
    {
        for(;j<n2-n1;j++)
        {
            A[p]=right[j];
            p++;
        }

    }
    else /*means all the elements of the right  array are copied but there can be elements in left */
    {
        for(;i<n2-n1+1;i++)
        {
            A[p]=left[i];
            p++;
        }
    }
}

when i am combing the arrays the loop will come out if only the i or j  index have reached boundry conditions and now in if else condition i am checking which index has achieved boundary conditions as if it j then i will simply copy all the elements of left array in A that is the final array or if it was i then i am copying all the remaining elements from left array . 

Here i tried to keep the previous program as it is ..with minimal changes ... so that you can understand the idea .. well other approaches are also possible .. 

as once a great mathematician said " there are infinitely many solutions possible for a single  problem " 

so try to program it and find newer approaches by yourself  

merge sort ( a program that will explain the working of whole merge sort )

well today we are going to learn about merge sort i think it is the very first program written in "analysis of algorithm  by coreman "
i am going to tell you the easiest approach. i want you to copy this program in your compiler and let it run... this program will unfold everything.

#include<stdio.h>
#include<conio.h>
void main()
{
     int i,array1[]={1,5,7,84,32,76,41,62,79,13};
     merge(array1,0,9);
    for( i=0;i<=9;i++)
    {
          printf("%d\n",array1[i]);
    }
}

void merge(int *A,int p,int n)
{
  if (p==n)
    {
    return;
    }
  else
   {

    int q=p+(n-p)/2;
    printf("now calling merge(A,%d,%d)\n",p,q);
    merge(A,p,q);
    printf(" now calling merge(A,%d,%d)\n",q+1,n);
    merge(A,q+1,n);
    printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
    combine(A,p,q,n);
   }
}
void combine(int *A,int p,int x,int n)
{
    int i = 0;
    int j=0;
    int n1 = p ;
    int left[10];
    int right[10];
    for( i=0;p<=x;i++,p++)
    {
            left[i] = A[p];
            printf("the element added in left now which is %d",left[i]);

    }
    left[i]=10000;

    for(i=0;(x+1)<=n;x++,i++)
    {
        right[i] = A[x+1];
        printf("the element added in right now which is  %d",right[i]);

    }
    right[i]=50000;
    printf("\n");
    for(i=0,j=0;n1<=n;n1++)
    {
        if(left[i]<right[j])
        {
            A[n1]=left[i];
            printf("the element added from left in A[%d] which is %d \n",n1,A[n1]);
            i++;
        }
        else
        {

            A[n1]= right[j];
            printf("the element added from right in A[%d] which is \n",A[n1]);
            j++;
        }
    }
}

here is the explanation well it is a method to sort numbers by divide and conquer algorithim

the idea is if you have to solve the smaller problems and somehow combine their results to solve the bigger ones

there are lot of techniques also for example dynamic programming and greedy based algo

and this is one among them

here what i am doing .. in order to sort the numbers

i am breaking the problems into smaller parts

as you can see i wrote merge(A,0,9)

i used array1 here

i think

so when i am calling it first it will enter into merge program

*function

not program

and there a smaller version of it would be called ie merge(A,0,2)

in actual i wrote it as merge (a,p,q )

where p is starting point

and q is the point upto which i should

and when it will enter into it it will again divide the array as now there are three elements .. the program would divide into two and one element

and here recursion come into picture

calling the function itself

and then the program would again try to divide the array which has two elements now in to two arrays of one and one

and as i know i don;t have to sort the single element because it is already sorted i will just return it .. so i rote the base case as you can see where i wrote p==n

return this value now the actual part is to combine two sorted array

and here the combining procedure/function is called

question : What is this left [i]=10000 for?

answer : actually i copied the left array in left[] and right one in right[]

and then while comparing it may be the case that all elements of first array will get copied first and then the i index will be one more than the actual one.

so i used a larger number(any large random number you can use but it should be greater than the elements present in both array ) so that while comparing it...that element won't be copied otherwise there will be some garbage value