Print Level Order binary tree Linked List implementation (BST)

/*Author:- Mufaddal Kagda */

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

/*Binary tree node implementation for Linked List*/
struct node
{
     
       struct node *llink;
       int info;
       struct node *rlink;
     
};
typedef struct node SNODE;

/*Queue node implementation for Linked List*/
struct qnode
{
SNODE *info;
struct qnode *link;
};
typedef struct qnode QNODE;



/* Functions for Creating Binary tree and displaying it in tree format */
void insert(SNODE **,int);
void display(SNODE **,int);
void bst(SNODE **,SNODE **);

/* Function to print the nodes of a binary tree in a level-wise manner format */
void printLevelOrder(SNODE **);
SNODE* dequeue(QNODE **);
void enqueue(QNODE **,QNODE **,SNODE **);


/* Function for inserting a node in binary search tree */
void insert(SNODE **proot,int val)
{
     SNODE *pnew,*pcurr;
   
     /* Setting Current node to the Root node of the binary tree */
     pcurr=*proot;
   
     /* Initialing new node of the binary tree */
     pnew=(SNODE*)malloc(sizeof(SNODE));
     pnew->llink=NULL;
     pnew->info=val;
     pnew->rlink=NULL;
   
      /* Initializing the binary tree root node if null*/
     if(*proot==NULL)
     {
          *proot=pnew;
     }
      /* if not null then search and place the node on the right position of the binary search tree*/
     else
     {
                 
                   bst(&pcurr,&pnew);
     }
}
/* Function for displaying binary tree nodes in tree format */
void display(SNODE **proot,int level)
{
     SNODE *pcurr;
     int i;
   
     pcurr=*proot;
     if(pcurr!=NULL)
     {
                    /* Print all the nodes of right tree from the root node */
                    display(&(pcurr->rlink),level+1);
                 
                    /* Print tab space according to the level */
                    for(i=1;i<level;i++)
                            printf("\t");
                                     
                    printf("%d\n\n",pcurr->info);
                    /* Print all the nodes of left tree from the root node */
                    display(&(pcurr->llink),level+1);
                 
     }
}
/* Function for searching and placing the node of binary tree nodes in a right position */
void bst(SNODE **proot,SNODE **pne)
{
        SNODE *pcurr,*pnew;
        pcurr=*proot;
        pnew=*pne;
     
        /*if node value not in binary search tree then find and place the node on right pos */
        if((pcurr->info)!=(pnew->info))
        {
                                       /* if new node value is less then the current node's value and its left link is not empty */
                                       if((pcurr->info > pnew->info)&&(pcurr->llink!=NULL))
                                       {
                                                       bst(&(pcurr->llink),&pnew);
                                       }
                                       /* if new node value is greater then the current node's value and its right link is not empty */
                                       else
                                       if((pcurr->info < pnew->info)&&(pcurr->rlink!=NULL))
                                       {
                                                       bst(&(pcurr->rlink),&pnew);
                                       }
                                       else
                                       /* if found a empty position then place it the new node according to the cond. in the binary tree */
                                           (pcurr->info > pnew->info) ? (pcurr->llink=pnew): (pcurr->rlink=pnew);
        }
}
/* Function for displaying binary tree nodes in Level wise mannner*/
void printLevelOrder(SNODE **proot)
{
   
     SNODE *pcurr;
     QNODE *pfront,*prear;
   
      /* initializing current ,front and rear node*/
     pcurr=*proot;
     pfront=NULL;
     prear=NULL;

     while(pcurr)
     {

                 printf("%d ", pcurr->info);

                 /*Enqueue left child */
 
                 if(pcurr->llink)
                 enqueue(&pfront, &prear, &(pcurr->llink));

                 /*Enqueue right child */
 
                 if(pcurr->rlink)
                 enqueue(&pfront, &prear, &(pcurr->rlink));

                 /*Dequeue node and make it pcurr or current node*/
                 if(pfront==NULL)
                 break;
                 pcurr = dequeue(&pfront);

     }
}
/* Function for Enqueueing a node in the queue*/
void enqueue(QNODE **apfront,QNODE **aprear,SNODE **pnew)
{
   
        QNODE *qnew;
         /* initialize the queue node*/
qnew=(QNODE *)malloc(sizeof(QNODE));
qnew->info=*pnew;
qnew->link=NULL;

   /* Initialize the queue if its is null*/
if(*apfront==NULL)
{
*apfront=qnew;
*aprear=qnew;
}
/*if queue not null then enqueue the node at the rear of the queue*/
else
{
             /* creating linkto the new node */
   (*aprear)->link=qnew;
 
    /* setting queue rear at the new node*/
   *aprear=qnew;
}


}
/* Function for dequeueing a node from the queue*/
SNODE* dequeue(QNODE **pfront)
{
QNODE *pdel;
SNODE *pnode;

pdel=*pfront;

     /*saving the info of the dequeued node */
pnode=pdel->info;

     /* deleting link of the node to dequeue it*/
(*pfront)=(*pfront)->link;

    /* Free memory for the dequeued node */
free(pdel);

/* Returning the dequeued node to the caller func*/
return pnode;

}


int main()
{
    SNODE *proot;
    proot=NULL;
 
     /* insertion of nodes in abinary tree*/
    insert(&proot,10);
    insert(&proot,7);
    insert(&proot,20);
    insert(&proot,1);
    insert(&proot,78);
    insert(&proot,9);
    insert(&proot,16);
    insert(&proot,4);
    insert(&proot,14);
 
     /* displaying nodes in a tree format horizontally which starts 10 as root node*/
    display(&proot,2);
 
     /* displaying nodesin a level wise mannner */
    printLevelOrder(&proot);
 
    getch();
}

Radix Sort with unique Random Input

/* RADIX SORT */

/* Author :- Mufaddal Kagda *//

#include <stdio.h>
#include<time.h>
#define MAX 10
void insq(int,int,int*);
int b[MAX][MAX];
void print(int *a)
{
  int i;
  printf("\n");
  for (i = 0; i <MAX; i++)
    printf("%d\t", a[i]);
}

void radixsort(int *a, int n)
{
  int i,j,l=0,len[10],pos=0,temp=10,k,e=1;
 
  while(l<3)
  {
    k=0;
    for(i=0;i<10;i++)
    {
    len[i]=-1;
      }
   
     printf("\n");
  for(i=0;i<n;i++)
  {
pos=(a[i]%temp)/e;
insq(pos,a[i],len);

}
printf("\n\n");

 
  for(i=0;i<n;i++)
{
   for(j=0;j<=len[i];j++)
   {

a[k]=b[i][j];
k++;
                       }
}

temp=temp*10;
e=e*10;
l++;

   
}
 
 

}

void insq(int pos,int val,int *len)
{
  int i,j;
  len[pos]=len[pos]+1;
 
  b[pos][len[pos]]=val;
  /* printf("\n\n\n");
  for(i=0;i<4;i++)
  for(j=0;j<4;j++)
  printf("%d",b[i][j]);
  printf("\n");*/
 
}


int main()
{
  int arr[MAX];
  time_t t;
  int i, n;
  srand(time(&t));
 
  for (i = 0; i < MAX; i++)
   arr[i]=rand()%1000;

  printf("\nARRAY  : ");
  print(arr);

  radixsort(arr,MAX);

  printf("\nSORTED : ");
  print(arr);
  printf("\n");
  getch();
  return 0;
}

Check for balanced parentheses in an Expression

Algorithm:
1) Now traverse the expression string exp.
    a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
    b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
2) After complete traversal, if there is some starting bracket left in stack then “not balanced”


Implementation :

/*  Author :- Mufaddal Kagda */

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
int info;
struct node *link;
};
typedef struct node SNODE;
int push(SNODE **,int);
int display(SNODE *);
bool areParenthesisBalanced(char exp[]);
bool isMatchingPair(char character1, char character2);
int pop(SNODE **);
int main()
{
SNODE *pnew,*ptop;
int rv,ch,k,val;
system("CLS");
ptop=NULL;
char exp[100];
    while(1)
    {
   system("CLS");
printf("\n1.Insert an expression.");
printf("\n2.exit");
printf("\nEnter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
  printf("\nEnter an Expression to check : ");
  scanf("%s",exp);
  if(areParenthesisBalanced(exp))
 printf("\n Balanced ");
   else
             printf("\n Not Balanced ");
             break;
       default:
exit(0);

        }
getch();
    }
 
     return 0;
}
int push(SNODE **aptop,int val)
{
SNODE *pnew;

pnew=(SNODE *)malloc(sizeof(SNODE));
pnew->info=val;
pnew->link=*aptop;

*aptop=pnew;
return 0;

}

int display(SNODE *pcurr)
{
while(pcurr !=NULL)
{
printf(" %d",pcurr->info);
pcurr=pcurr->link;
}
return 0;
}

int pop(SNODE **ptop)
{
SNODE *pdel;
int ret;
if(*ptop==NULL)
return -1;
pdel=*ptop;
(*ptop)=(*ptop)->link;
ret=pdel->info;
free(pdel);
return ret;

}
bool isMatchingPair(char character1, char character2)
{
   if(character1 == '(' && character2 == ')')
     return 1;
   else if(character1 == '{' && character2 == '}')
     return 1;
   else if(character1 == '[' && character2 == ']')
     return 1;
   else
     return 0;
}

bool areParenthesisBalanced(char exp[])
{
   int i = 0;

 
    SNODE *stack = NULL;

 
   while(exp[i])
   {
 
      if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
        push(&stack, exp[i]);

 
      if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
      {

 
         if(stack == NULL)
           return 0;

 
         else if ( !isMatchingPair(pop(&stack), exp[i]) )
           return 0;
      }
      i++;
   }

 
   if(stack == NULL)
     return 1; /*balanced*/
   else
     return 0;  /*not balanced*/
}