Programming Geek
Rated 4.1/5 based on 446 reviews

Binary Search Tree

Binary Search Tree : Binary search tree is a tree in which the left descendant has data lower than the node and the right descendant has data greater than the node. A binary search tree has several applications. It can be used to detect duplicates, sort a list, efficient search and delete the items. The inorder traversal of a binary search tree prints the elements in increasing order.

C program implementing binary search tree.

//Binary Search Tree
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

typedef struct node
{
 int data;
 struct node*left;
 struct node*right;
}node;

//insert node in a binary search tree
void insert(node**bst,int n)
{ 
 
 if(*bst==NULL)//if node is NULL than create a node
 {
  *bst=(node*)malloc(sizeof(node));
  (*bst)->data=n;
  (*bst)->left=NULL;
  (*bst)->right=NULL;
 }
 else
 { //if number is less than node data than insert in left subtree
  if(n<(*bst)->data)
  insert(&((*bst)->left),n);
  else//insert in right subtree
  insert(&((*bst)->right),n);
 }
}

//search for a parent node and node to be deleted
void search(node**bst,node**par,node**del,int*found,int n)
{ node*temp=*bst;
 if(temp==NULL)
 {
  *found=0;
  return;
 }
 *par=NULL;
 while(temp!=NULL)
 {
  if(temp->data==n)
  {
   *del=temp;
   *found=1;
   return;
  }
  *par=temp;
  if(n<temp->data)
  temp=temp->left;
  else
  temp=temp->right;
  
 }
 
}

//delete a node and adjust the binary search tree
void delete(node**bst,int n)
{ node*par=NULL,*del=NULL,*par1=NULL,*del1=NULL,*temp=NULL;
 int flag=0;
 
 //Tree is empty
 if(*bst==NULL)
 {
  printf("\nTree is empty!!!");
  return;
 }
 
 //search for parent node and node to be deleted
 search(bst,&par,&del,&flag,n);
 
 //if node is not present
 if(flag==0)
 {
  printf("\n Data not found");
  return;
 }
 
 //if node found
 
 //if left and right subtree of the concerned node is not empty
 if(del->left!=NULL && del->right!=NULL)
 { 
  
  //find inorder successor
  del1=del->right;
  while(del1->left!=NULL)
  {
   par1=del1;
   del1=del1->left;
  }
  
  
  par1->left=del1->right;//set left link of parent of inorder successor to child of successor
  del1->left=del->left;//set left link of successor to the left descendant of to be deleted node
  del1->right=del->right;//set right link of successor to the right descendant of to be deleted node
  //delete the concerned node
  if(par->data>del->data) 
  par->left=del1;
  else
  par->right=del1;
  free(del);
  return;
 }
 
 if(del->left==NULL && del->right==NULL)
 {
  if(del->data>par->data)
  par->right=NULL;
  else
  par->left=NULL;
  free(del);
  return;
 }
 
 if(del->right!=NULL)
 {
  if(del->data>par->data)
  par->right=del->right;
  else
  par->left=del->right;
  free(del);
  return;
 }
 if(del->left!=NULL)
 {
  if(del->data>par->data)
  par->right=del->left;
  else
  par->left=del->left;
  free(del);
  return;
 }
 
}

//traverse the tree in inorder
void inorder(node*bt)
{
 if(bt!=NULL)
 {
  inorder(bt->left);
  printf("%d\t",bt->data);
  inorder(bt->right);
 }
}

//traverse the tree in preorder
void preorder(node*bt)
{
 if(bt!=NULL)
 {
  printf("%d\t",bt->data);
  preorder(bt->left);
  preorder(bt->right);
 }
}

//traverse the tree in postorder
void postorder(node*bt)
{
 if(bt!=NULL)
 {
  postorder(bt->left);
  postorder(bt->right);
  printf("%d\t",bt->data);
  
 }
}


void main()
{
 node*bst=NULL;
 insert(&bst,6);
 insert(&bst,2);
 insert(&bst,1);
 insert(&bst,5);
 insert(&bst,3);
 insert(&bst,4);
 insert(&bst,9);
 insert(&bst,7);
 insert(&bst,10);
 inorder(bst);
 printf("\n");
 preorder(bst);
 delete(&bst,2);
 printf("\n");
 postorder(bst);
 
}




Binary Tree using Linked List

The following C program build a binary tree using linked list. The tree can be traversed in in-order, pre-order or post-order.

Traversal Algorithm:

Preorder :
         
            1) Traverse the root.
            2) Traverse the left subtree in preorder.
            3) Traverse the right subtree in preorder.

Inorder:
     
            1) Traverse the left subtree in inorder.
            2) Traverse the root.
            3)  Traverse the right subtree in inorder.

Postorder:

            1) Traverse the left subtree in postorder.
            2)  Traverse the right subtree in postorder.
            3) Traverse the root.

//Binary tree using linked list
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

int count=1;

typedef struct node
{
 int data;
 struct node*left;
 struct node*right;
}node;

void insert(node**bt,int n)
{
 if(*bt==NULL)
 {
  *bt=(node*)malloc(sizeof(node));
  (*bt)->data=n;
  (*bt)->left=NULL;
  (*bt)->right=NULL;
  count++;
 }
 else
 {
 if(count%2==0)
 insert(&((*bt)->left),n);
 else
 insert(&((*bt)->right),n);
 }
}

//traverse the tree in inorder
void inorder(node*bt)
{
 if(bt!=NULL)
 {
  inorder(bt->left);
  printf("%d\t",bt->data);
  inorder(bt->right);
 }
}

//traverse the tree in preorder
void preorder(node*bt)
{
 if(bt!=NULL)
 {
  printf("%d\t",bt->data);
  preorder(bt->left);
  preorder(bt->right);
 }
}

//traverse the tree in postorder
void postorder(node*bt)
{
 if(bt!=NULL)
 {
  postorder(bt->left);
  postorder(bt->right);
  printf("%d\t",bt->data);
  
 }
}

void main()
{
 node*bt=NULL;
 insert(&bt,1);
 insert(&bt,2);
 insert(&bt,3);
 insert(&bt,4);
 insert(&bt,5);
 insert(&bt,6);
 inorder(bt);
 printf("\n");
 preorder(bt);
 printf("\n");
 postorder(bt);
}


Binary Tree Using Array

An array can be converted into a binary tree.

      1) Parent : Parent of a node at index lies at (n-1)/2 except the root node.
   
      2) Left Child : Left child of a node at index n lies at (2*n+1).
   
      3) Right Child : Right child of a node at index n lies at (2*n+2).
   
     4) Left Sibling : left Sibling of a node at index n lies at (n-1).
   
     5) Right Sibling : Right sibling of a node at index n lies at (n+1).

C program for converting a list of array into a binary tree.

 
//Binary tree Using array
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

typedef struct node
{
 struct node*left;
 struct node*right;
 char data;
}node;

node* insert(char c[],int n)
{ node*tree=NULL;
 if(c[n]!='\0')
 {
  tree=(node*)malloc(sizeof(node));
  tree->left=insert(c,2*n+1);
  tree->data=c[n];
  tree->right=insert(c,2*n+2);
 }
 return tree;
}
//traverse the tree in inorder
void inorder(node*tree)
{
 if(tree!=NULL)
 {
  inorder(tree->left);
  printf("%c\t",tree->data);
  inorder(tree->right);
 }
}

void main()
{
 node*tree=NULL;
 char c[]={'A','B','C','D','E','F','\0','G','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0'};
 tree=insert(c,0);
 inorder(tree);
}

Solution of Tower of Hanoi Problem

Problem : There are three pegs start, auxiliary and destination. Start peg contains certain number of disks such that smaller disk is on the bigger disk. The problem is to move all the disks from start peg to destination peg following two conditions:

               1) Only one pile can be moved at a time and only from the top.
               2) A larger disk can not be placed on a smaller disk.

Algorithm :
               1) Move the top n-1 disks from start to auxiliary peg.
               2) Move the top disk from start to destination.
               3) Move the top n-1 disks from auxiliary peg to destination peg.

The movement of four disks is illustrated below:

     


The C program implementing the above algorithm:




     
//C program for solving Tower of Hanoi problem
/**
*
*@author VIKASH VIK VIKASHVVERMA
* 
*/

#include<stdio.h>

void towerofhanoi(int n,char start[], char aux[], char destination[])
{
 //base condition
 if(n==1)
 {
  printf("\n%s-->%s",start,destination);
  return;
 }
 
 //move n-1 disks from start peg to auxiliary peg
 towerofhanoi(n-1,start,destination,aux);
 //move last disks to destination peg
 printf("\n%s-->%s",start,destination);
 //move n-1 disks from auxiliary peg to destination peg
 towerofhanoi(n-1,aux,start,destination);
}

void main()
{
 int n;
 printf("Enter no. of disks:");
 
 //get number of disks
 scanf("%d",&n);
 printf("Movement of disks are : ");
 //solve Tower of Hanoi problem recursively by calling towerofhanoi(-,-,-,-) function
 towerofhanoi(n,"A","B","C");
}

Reversing a Linked List

Reversing a linked list means changing the order of the node i. e. the first node becomes the last node and the last node becomes the first node.  A linked list can be reversed using three variable called pre(previous node pointer), cur (current node pointer) and next(next node pointer) and performing following operations while next is not null:
               
          1) make cur link part to point to pre.
          2)make pre to point to pre.
          3) make next to point to next node.
          4)assign next to cur as this will be current node in next iteration.

This is illustrated in following C program:



//reversing  a linked list
/**
*
*@author VIKASH VIK VIKASHVVERMA
*
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data;
 struct node*next;
}node;

void add(node**s,int num)
{
 node*temp=(node*)malloc(sizeof(node));
 temp->data=num;
 temp->next=*s;
 *s=temp;
}

void traverse(node*s)
{
 while(s!=NULL)
 {
  printf("%d\t",s->data);
  s=s->next;
 }
}
void reverse(node**s)
{
 node*pre=NULL,*cur=NULL,*next=NULL;
 cur=*s;
 next=*s;
 while(next!=NULL)
 {
 
 next=cur->next;
 cur->next=pre;
 pre=cur;
 cur=next;
 
 }
 *s=pre;
}


void main()
{
 node*n=NULL;
 
 add(&n,5);
 add(&n,7);
 add(&n,18);
 add(&n,12);
 add(&n,78);
 add(&n,-13);
 traverse(n);
 reverse(&n);
 traverse(n);
}


Ascending Order Linked List

An ascending order linked list is the list sorted in increasing order of data. During addition one needs to traverse the list until the element having data value same or higher is not found and then, create the node and insert it there.

The following C program builds a linked list in ascending order.


//ascending order linked list
/**
*
*@author VIKASH VIK VIKASHVVERMA
*
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data;
 struct node*next;
}node;

void add(node**s,int num)
{
 node*temp;
 if(*s==NULL||num<(*s)->data)
 {
  temp=(node*)malloc(sizeof(node));
  temp->data=num;
  temp->next=*s;
  *s=temp;
 }
 else
 {
  temp=*s;
  while(temp!=NULL)
  {
   if(temp->data<=num&&(temp->next==NULL || temp->next->data>num))
   {
    node*temp1=(node*)malloc(sizeof(node));
    temp1->data=num;
    temp1->next=temp->next;
    temp->next=temp1;
    return;
   }
   temp=temp->next;
  }
 }
 
}
void traverse(node*s)
{
 while(s!=NULL)
 {
  printf("%d\t",s->data);
  s=s->next;
 }
}

void main()
{
 node*n=NULL;
 
 add(&n,5);
 add(&n,7);
 add(&n,18);
 add(&n,12);
 add(&n,78);
 add(&n,-13);
 traverse(n);
}



Basic Operations On Linked List

Linked List is a data structure consisting of a group of nodes connected together. A node of linked list is consisted of data part and a pointer to next node. If there is only one node than the pointer to next node has value NULL. Usually in singly linked list, last node's pointer has NULL value. The pseudo code of a typical linked list is as:

     struct node
     {
           int data;
           struct node*next;
     }


A linked list can hold any type of data. This is one of the advantages of linked list over typical array. Linked list grows dynamically. Since the nodes are stored randomly, memory is utilized efficiently. A logical  representation of linked list is shown in the diagram.



The basic operation performed on linked list like traversal,appending, addition at beginning, deletion of a node etc is implemented in following C program.

//Basic operations performed on a lined list like traversal, addition, deletion 
/**
 *
 * @author VIKASH VIK VIKASHVVERMA
 */

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data;
 struct node*next;
}node;

void append(node**s,int num)
{
 node*temp;
 if(*s==NULL)
 {
 temp=(node*)malloc(sizeof(node));
 temp->data=num;
 temp->next=NULL;
 *s=temp;
 
 }
 else
 {
 temp=*s;
 
 while(temp->next!=NULL)
 temp=temp->next;
  
 node*temp1=(node*)malloc(sizeof(node));
 temp1->data=num;
 temp1->next=NULL;
 temp->next=temp1;
 }
}

void addatbeg(node**s,int num)
{
 node*temp=(node*)malloc(sizeof(node));
 temp->data=num;
 temp->next=*s;
 *s=temp;
}

void addafter(node**s,int num,int pos)
{
 node*temp;
 int count=1;
 temp=*s;
 
 while(count<pos)
 { 
  if(temp==NULL)
  {
   printf("\nless than %d elements",pos);
   exit(0);
  }
  temp=temp->next;
  count++;
 }
 
 node*temp1=(node*)malloc(sizeof(node));
 temp1->data=num;
 temp1->next=temp->next;
 temp->next=temp1;
}

void traverse(node*s)
{ printf("\n");
 while(s!=NULL)
 {
  printf("%d\t",s->data);
  s=s->next;
 }
}

void delete(node**s,int num)
{
 node*prev=NULL,*temp=NULL;
 temp=*s;
 
 while(temp!=NULL)
 {
  if(temp->data==num)
  {
   if(temp==*s)
   *s=temp->next;
   else
   prev->next=temp->next;
   
   free(temp);
   return;
  }
  else
  {
   prev=temp;
   temp=temp->next;
  }
  
 }
}
void main()
{
 node*n=NULL;
 
 append(&n,5);
 append(&n,7);
 append(&n,18);
 append(&n,12);
 append(&n,78);
 append(&n,-13);
 traverse(n);
 addatbeg(&n,25);
 traverse(n);
 addafter(&n,19,3);
 traverse(n);
 delete(&n,12);
 traverse(n);
 
}


Stack Implementation in C

Stack is a "last in first out" (LIFO) data structure in which the last element added is the first element to be removed. The addition of an element on stack is called PUSH and the deletion of the element is called POP operation. A typical stack is illustrated below:


Stack finds a large number of applications in various area of computer science like stack area during execution of a program, tower of Hanoi or any other recursive program.

Some stack terminology are:

PUSH : It is the process of adding an element at the top of the stack. If stack is full then stack overflow error is shown i.e. no more elements can be added.

POP : It is the process of removing an element from the top of the stack, If stack is empty then stack underflow error is shown i.e. no element can be deleted.

TOP : It always points to the top of the stack.

An implementation of stack in c is as below:

#include<stdio.h>
#include<stdlib.h>

typedef struct stack
{
 int size;
 int capacity;
 int*elements;
}stack;

stack*init(int max_elements)
{
 stack*s=(stack*)malloc(sizeof(stack));
 s->capacity=max_elements;
 s->size=0;
 s->elements=(int*)malloc(sizeof(int)*max_elements);
 return s;
}

void push(stack*s,int num)
{
 if(s->size==s->capacity)
 {
  printf("\n stack is full!!!");
  return;
 }
 s->elements[s->size++]=num;
 
}

void pop(stack*s)
{
 if(s->size==0)
 {
  printf("\nstack is empty!!!");
  return;
 }
 s->size--;
}

int top(stack*s)
{
 if(!s->size)
 {
  printf("\nstack is empty!!!");
  exit(0);
 }
 return s->elements[s->size-1];
 
}

void main()
{
 stack *s = init(9);
        push(s,12);
        push(s,15);
        push(s,58);
        push(s,32);
        printf("Top element is %d\n",top(s));
        pop(s);
        printf("Top element is %d\n",top(s));
        pop(s);
        printf("Top element is %d\n",top(s));
        pop(s);
        printf("Top element is %d\n",top(s));


}