Fixed C Programming Examples: Calendar, Stack, Queue, Linked List, Tree

Fixed C Programming Examples

1. Weekly Calendar Program

This program creates, reads, displays and frees a weekly calendar using a structure.

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

#define NUM_DAYS_IN_WEEK 7

typedef struct {
    char *acDayName;
    int iDate;
    char *acActivity;
} DAYTYPE;

void fnFreeCal(DAYTYPE *);
void fnDispCal(DAYTYPE *);
void fnReadCal(DAYTYPE *);
DAYTYPE *fnCreateCal();

int main()
{
    DAYTYPE *weeklyCalendar = fnCreateCal();
    fnReadCal(weeklyCalendar);
    fnDispCal(weeklyCalendar);
    fnFreeCal(weeklyCalendar);
    return 0;
}

DAYTYPE *fnCreateCal()
{
    DAYTYPE *calendar = (DAYTYPE *)malloc(NUM_DAYS_IN_WEEK * sizeof(DAYTYPE));
    for (int i = 0; i < NUM_DAYS_IN_WEEK; i++)
    {
        calendar[i].acDayName = NULL;
        calendar[i].iDate = 0;
        calendar[i].acActivity = NULL;
    }
    return calendar;
}

void fnReadCal(DAYTYPE *calendar)
{
    char cChoice;
    for (int i = 0; i < NUM_DAYS_IN_WEEK; i++)
    {
        printf("Do you want to enter details for day %d [Y/N]: ", i + 1);
        scanf(" %c", &cChoice);
        getchar();
        if (tolower(cChoice) == 'n')
            continue;

        char nameBuffer[50];
        printf("Day Name: ");
        scanf("%s", nameBuffer);
        calendar[i].acDayName = strdup(nameBuffer);

        printf("Date: ");
        scanf("%d", &calendar[i].iDate);

        char activityBuffer[100];
        printf("Activity: ");
        scanf(" %[^\n]", activityBuffer); // Read the entire line including spaces
        calendar[i].acActivity = strdup(activityBuffer);
        printf("\n");
        getchar(); // remove trailing enter character in input buffer
    }
}

void fnDispCal(DAYTYPE *calendar)
{
    printf("\nWeek's Activity Details:\n");
    for (int i = 0; i < NUM_DAYS_IN_WEEK; i++)
    {
        printf("Day %d:\n", i + 1);
        if (calendar[i].iDate == 0)
        {
            printf("No Activity\n\n");
            continue;
        }
        printf(" Day Name: %s\n", calendar[i].acDayName);
        printf(" Date: %d\n", calendar[i].iDate);
        printf(" Activity: %s\n\n", calendar[i].acActivity);
    }
}

void fnFreeCal(DAYTYPE *calendar)
{
    for (int i = 0; i < NUM_DAYS_IN_WEEK; i++)
    {
        free(calendar[i].acDayName);
        free(calendar[i].acActivity);
    }
    free(calendar);
}

2. String Pattern Replacement

This program finds every occurrence of a pattern in a main string and replaces it with a replacement string.

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

int main()
{
    char acMainStr[200], acSrchStr[30], acRepStr[30], acResStr[200], acCopyStr[200];
    int i = 0, j = 0, k = 0, l, iMtchCnt, iStop, len, iNumOfMatch = 0;

    printf("\nEnter the main string :\n");
    scanf(" %[^\n]", acMainStr);
    printf("\nEnter the Pattern string :\n");
    scanf(" %[^\n]", acSrchStr);
    printf("\nEnter the Replace string :\n");
    scanf(" %[^\n]", acRepStr);

    strcpy(acCopyStr, acMainStr);

    for (i = 0; i < (strlen(acMainStr) - strlen(acSrchStr) + 1); i++)
    {
        iMtchCnt = 0;
        for (j = 0; j < strlen(acSrchStr); j++)
        {
            if (acMainStr[i + j] == acSrchStr[j])
            {
                iMtchCnt++;
            }
            else
            {
                break;
            }
        }
        if (iMtchCnt == strlen(acSrchStr))
        {
            iNumOfMatch++;
            for (k = 0; k < i; k++)
            {
                acResStr[k] = acMainStr[k];
            }
            iStop = k + strlen(acSrchStr);
            acResStr[k] = '\0';
            strcat(acResStr, acRepStr);
            len = strlen(acResStr);
            for (k = iStop, l = 0; acMainStr[k] != '\0'; k++, l++) // copy rest of original string
            {
                acResStr[len + l] = acMainStr[k];
            }
            acResStr[len + l] = '\0';
            strcpy(acMainStr, acResStr);
        }
    }

    printf("\nInput Text :\n");
    printf("%s\n", acCopyStr);
    if (iNumOfMatch > 0)
    {
        printf("\n%d matches occurred\n\nText after replacing matched patterns is shown below\n", iNumOfMatch);
        printf("\n%s\n", acResStr);
    }
    else
    {
        printf("\nPattern String not found in Text\n");
    }
    return 0;
}

3. Stack Operations with Palindrome Check

This program implements a stack using an array, with push, pop, display, peek, overflow and underflow demonstrations, and a palindrome check.

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

#define MAX 4

bool fnStkFull(int);
bool fnStkEmpty(int);
void fnPush(int [], int, int*);
int fnPop(int [], int*);
void fnDisplay(int [], int);
int fnPeek(int [], int);
bool fnChkPalindrome(int);

int main(void)
{
    int stkArray[MAX];
    int top = -1;
    int iElem, iChoice;

    for (;;)
    {
        printf("\nSTACK OPERATIONS\n");
        printf("====================");
        printf("\n 1.Push\n 2.Pop\n 3.Display\n 4.Peek\n 5.CheckPalindrome\n 6.Demonstrate Overflow\n 7.Demonstrate Underflow\n 8.EXIT\n");
        printf("Enter your choice\n");
        scanf("%d", &iChoice);

        switch (iChoice)
        {
        case 1:
            if (!fnStkFull(top))
            {
                printf("\nEnter element to be pushed onto the stack\n");
                scanf("%d", &iElem);
                fnPush(stkArray, iElem, &top);
            }
            else
            {
                printf("\nStack Overflow\n");
            }
            break;
        case 2:
            if (!fnStkEmpty(top))
            {
                iElem = fnPop(stkArray, &top);
                printf("\nPopped Element is %d\n", iElem);
            }
            else
            {
                printf("\nStack Underflow\n");
            }
            break;
        case 3:
            if (fnStkEmpty(top))
            {
                printf("\nStack Empty\n");
            }
            else
            {
                fnDisplay(stkArray, top);
            }
            break;
        case 4:
            if (!fnStkEmpty(top))
            {
                iElem = fnPeek(stkArray, top);
                printf("\nElement at the top of the stack is %d\n", iElem);
            }
            else
                printf("\nEmpty Stack\n");
            break;
        case 5:
            printf("\nEnter number to be checked for a palindrome : ");
            scanf("%d", &iElem);
            if (fnChkPalindrome(iElem))
            {
                printf("\n%d is a palindrome\n", iElem);
            }
            else
            {
                printf("\n%d is not a palindrome\n", iElem);
            }
            break;
        case 6:
            if (!fnStkFull(top))
                printf("\nThere are currently %d elements in Stack\nPush %d elements for Stack to overflow", top + 1, MAX - (top + 1));
            while (!fnStkFull(top))
            {
                printf("\nEnter an element : ");
                scanf("%d", &iElem);
                fnPush(stkArray, iElem, &top);
            }
            printf("\nStack Overflow cannot push elements onto the stack\n");
            break;
        case 7:
            if (!fnStkEmpty(top))
                printf("\nThere are currently %d elements in Stack\nPop out %d elements for Stack to Underflow", top + 1, MAX - (top + 1));
            while (!fnStkEmpty(top))
            {
                iElem = fnPop(stkArray, &top);
                printf("\nPopped Element is %d\n", iElem);
            }
            printf("\nStack Underflow cannot pop elements from the stack\n");
            break;
        case 8:
            exit(1);
        default:
            printf("\nWrong choice\n");
        }
    }
    return 0;
}

bool fnStkFull(int t)
{
    return ((t == MAX - 1) ? true : false);
}

bool fnStkEmpty(int t)
{
    return ((t == -1) ? true : false);
}

void fnPush(int stk[], int iElem, int *t)
{
    *t = *t + 1;
    stk[*t] = iElem;
}

int fnPop(int stk[], int *t)
{
    int iElem;
    iElem = stk[*t];
    *t = *t - 1;
    return iElem;
}

void fnDisplay(int stk[], int t)
{
    int i;
    printf("\nStack Contents are: \n");
    for (i = t; i > -1; --i)
    {
        printf("\t%d\n", stk[i]);
    }
    printf("Stack has %d elements\n", t + 1);
}

int fnPeek(int stk[], int t)
{
    return stk[t];
}

bool fnChkPalindrome(int iVal)
{
    int palStk[10];
    int t = -1, iDig, iRev = 0;
    int iCopy = iVal;
    while (iCopy != 0)
    {
        iDig = iCopy % 10;
        fnPush(palStk, iDig, &t);
        iCopy /= 10;
    }
    int p = 0;
    while (p <= t)
    {
        iDig = palStk[p];
        iRev = iRev * 10 + iDig;
        p++;
    }
    if (iRev == iVal)
        return true;
    else
        return false;
}

4. Infix to Postfix Conversion

This program converts a valid infix expression into a postfix expression using a stack.

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

#define STK_SIZE 10

void fnPush(char [], int*, char);
char fnPop(char [], int*);
int fnPrecd(char);

int main()
{
    int i, j = 0;
    char acExpr[50], acStack[50], acPost[50], cSymb;
    int top = -1;

    printf("\nEnter a valid infix expression : \n");
    scanf("%s", acExpr);

    fnPush(acStack, &top, '#');
    for (i = 0; acExpr[i] != '\0'; ++i)
    {
        cSymb = acExpr[i];
        if (isalnum(cSymb))
        {
            acPost[j++] = cSymb;
        }
        else if (cSymb == '(')
        {
            fnPush(acStack, &top, cSymb);
        }
        else if (cSymb == ')')
        {
            while (acStack[top] != '(')
            {
                acPost[j++] = fnPop(acStack, &top);
            }
            fnPop(acStack, &top);
        }
        else
        {
            while (fnPrecd(acStack[top]) >= fnPrecd(cSymb))
            {
                if ((cSymb == '^') && (acStack[top] == '^'))
                    break;
                acPost[j++] = fnPop(acStack, &top);
            }
            fnPush(acStack, &top, cSymb);
        }
    }
    while (acStack[top] != '#')
    {
        acPost[j++] = fnPop(acStack, &top);
    }
    acPost[j] = '\0';

    printf("\nInfix Expression is :%s\n", acExpr);
    printf("\nPostfix Expression is :%s\n", acPost);
    return 0;
}

void fnPush(char Stack[], int *t, char elem)
{
    *t = *t + 1;
    Stack[*t] = elem;
}

char fnPop(char Stack[], int *t)
{
    char elem;
    elem = Stack[*t];
    *t = *t - 1;
    return elem;
}

int fnPrecd(char ch)
{
    int iPrecdVal = 0;
    switch (ch)
    {
    case '#': iPrecdVal = -1; break;
    case '(': iPrecdVal = 0; break;
    case '+':
    case '-': iPrecdVal = 1; break;
    case '%':
    case '*':
    case '/': iPrecdVal = 2; break;
    case '^': iPrecdVal = 3; break;
    }
    return iPrecdVal;
}

5. Postfix Expression Evaluation

This program evaluates a single-digit postfix expression using a stack.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

void push(int [], int*, int);
int pop(int [], int*);

int main()
{
    int iastack[50], i, op1, op2, res;
    char expr[50], symb;
    int top = -1;

    printf("\nEnter a valid postfix expression : \n");
    scanf("%s", expr);

    for (i = 0; i < strlen(expr); i++)
    {
        symb = expr[i];
        if (isdigit(symb))
        {
            push(iastack, &top, symb - '0');
        }
        else
        {
            op2 = pop(iastack, &top);
            op1 = pop(iastack, &top);
            switch (symb)
            {
            case '+': res = op1 + op2; break;
            case '-': res = op1 - op2; break;
            case '*': res = op1 * op2; break;
            case '/': res = op1 / op2; break;
            case '%': res = op1 % op2; break;
            case '^': res = (int)pow(op1, op2); break;
            }
            push(iastack, &top, res);
        }
    }
    res = pop(iastack, &top);
    printf("\nValue of %s expression is : %d\n", expr, res);
    return 0;
}

void push(int Stack[], int *t, int elem)
{
    *t = *t + 1;
    Stack[*t] = elem;
}

int pop(int Stack[], int *t)
{
    int elem;
    elem = Stack[*t];
    *t = *t - 1;
    return elem;
}

6. Tower of Hanoi

This program prints the sequence of moves for the Tower of Hanoi problem using recursion.

#include <stdio.h>

void towers(int, char, char, char);

int main()
{
    int num;
    printf("Enter the number of disks : ");
    scanf("%d", &num);
    printf("The sequence of moves involved in the Tower of Hanoi are :\n");
    towers(num, 'A', 'C', 'B');
    printf("\n");
    return 0;
}

void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {
        printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
        return;
    }
    towers(num - 1, frompeg, auxpeg, topeg);
    printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg);
    towers(num - 1, auxpeg, topeg, frompeg);
}

7. Circular Queue of Characters

This program implements a circular queue with insert, delete and display operations.

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

#define SIZE 5

void insert(char [], int*, int*, char);
char del(char [], int*, int*);
void display(char [], int, int);
bool qfull(int, int);
bool qempty(int, int);

int main()
{
    char q[SIZE];
    int f = -1, r = -1;
    int ch;
    char elem;

    for (;;)
    {
        printf("\nQueue Operations\n");
        printf("=========");
        printf("\n1.Qinsert\n2.Qdelete\n3.Qdisplay\n4.Exit\n");
        printf("Enter your choice\n");
        scanf("%d", &ch);
        getchar();
        switch (ch)
        {
        case 1:
            if (!qfull(f, r))
            {
                printf("\nEnter an element : ");
                scanf("%c", &elem);
                insert(q, &f, &r, elem);
            }
            else
            {
                printf("\nQueue is Full\n");
            }
            break;
        case 2:
            if (!qempty(f, r))
            {
                elem = del(q, &f, &r);
                printf("\nDeleted element is %c\n", elem);
            }
            else
            {
                printf("\nQueue is Empty\n");
            }
            break;
        case 3:
            if (!qempty(f, r))
            {
                printf("\nContents of the Queue is \n");
                display(q, f, r);
            }
            else
            {
                printf("\nQueue is Empty\n");
            }
            break;
        case 4:
            exit(0);
        default:
            printf("\nInvalid choice\n");
            break;
        }
    }
    return 0;
}

bool qfull(int fr, int rr)
{
    if ((rr + 1) % SIZE == fr)
        return true;
    else
        return false;
}

bool qempty(int fr, int rr)
{
    if (fr == -1)
        return true;
    else
        return false;
}

void insert(char queue[], int *f, int *r, char val)
{
    if (*r == -1)
    {
        *f = *f + 1;
        *r = *r + 1;
    }
    else
        *r = (*r + 1) % SIZE;
    queue[*r] = val;
}

char del(char queue[], int *f, int *r)
{
    char el;
    el = queue[*f];
    if (*f == *r)
    {
        *f = -1;
        *r = -1;
    }
    else
    {
        *f = (*f + 1) % SIZE;
    }
    return el;
}

void display(char queue[], int fr, int rr)
{
    int i;
    if (fr <= rr)
    {
        for (i = fr; i <= rr; i++)
        {
            printf("%c\t", queue[i]);
        }
        printf("\n");
    }
    else
    {
        for (i = fr; i <= SIZE - 1; i++)
        {
            printf("%c\t", queue[i]);
        }
        for (i = 0; i <= rr; i++)
        {
            printf("%c\t", queue[i]);
        }
        printf("\n");
    }
}

8. Singly Linked List of Students

This program maintains a singly linked list of student records with insert and delete operations at both ends and a display function.

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

struct node
{
    char usn[11], name[40], prog[4];
    int sem;
    char ph[11];
    struct node *link;
};

typedef struct node* PTR;

PTR get(void);
void freeN(PTR);
PTR insrear(PTR);
PTR delfront(PTR);
PTR insfront(PTR);
PTR delrear(PTR);
void disp(PTR);

int main()
{
    PTR first = NULL;
    int ch, num, i;

    printf("\nEnter the number of Students N : ");
    scanf("%d", &num);
    for (i = 0; i < num; i++)
    {
        printf("\nEnter Data for Node %d :\n", i + 1);
        first = insfront(first);
    }

    for (;;)
    {
        printf("\nQUEUE OPERATIONS\n");
        printf("========");
        printf("\n1.Insert Front\n2.Insert Rear\n3.Delete Front\n4.Delete Rear\n5.Display\n6.Exit\n");
        printf("\nEnter your choice\n");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1: first = insfront(first); break;
        case 2: first = insrear(first); break;
        case 3: first = delfront(first); break;
        case 4: first = delrear(first); break;
        case 5: disp(first); break;
        case 6: exit(0);
        }
    }
    return 0;
}

PTR get()
{
    PTR newborn;
    newborn = (PTR)malloc(sizeof(struct node));
    if (newborn == NULL)
    {
        printf("\nMemory Overflow");
        exit(0);
    }
    printf("\nEnter USN : ");
    scanf("%s", newborn->usn);
    printf("\nEnter name : ");
    scanf("%s", newborn->name);
    printf("\nEnter Program name : ");
    scanf("%s", newborn->prog);
    printf("\nEnter semester : ");
    scanf("%d", &newborn->sem);
    printf("\nEnter Phone no : ");
    scanf("%s", newborn->ph);
    return newborn;
}

void freeN(PTR x)
{
    free(x);
}

PTR insrear(PTR first)
{
    PTR temp, cur;
    temp = get();
    temp->link = NULL;
    if (first == NULL)
        return temp;
    cur = first;
    while (cur->link != NULL)
    {
        cur = cur->link;
    }
    cur->link = temp;
    return first;
}

PTR delfront(PTR first)
{
    PTR temp;
    if (first == NULL)
    {
        printf("\nSLL is empty cannot delete\n");
        return first;
    }
    temp = first;
    first = first->link;
    printf("\nNode deleted is %s\n", temp->name);
    freeN(temp);
    return first;
}

void disp(PTR first)
{
    PTR curr;
    int count = 0;
    if (first == NULL)
    {
        printf("\nSLL is empty\n");
        return;
    }
    printf("\nThe contents of SLL are :\n");
    curr = first;
    printf("\nUSN\t\tName\tProgram\tSem\tPhone num");
    while (curr != NULL)
    {
        printf("\n%10s\t%s\t%s\t%d\t%s", curr->usn, curr->name, curr->prog, curr->sem, curr->ph);
        curr = curr->link;
        count++;
    }
    printf("\n\nSLL has %d nodes\n", count);
}

PTR insfront(PTR first)
{
    PTR temp;
    temp = get();
    temp->link = first;
    first = temp;
    return first;
}

PTR delrear(PTR first)
{
    PTR cur, prev;
    if (first == NULL)
    {
        printf("\nSLL is empty cannot delete\n");
        return first;
    }
    prev = NULL;
    cur = first;
    if (cur->link == NULL)
    {
        printf("\nNode deleted for %s\n", cur->name);
        freeN(cur);
        return NULL;
    }
    while (cur->link != NULL)
    {
        prev = cur;
        cur = cur->link;
    }
    prev->link = cur->link;
    printf("\nNode deleted for %s\n", cur->name);
    freeN(cur);
    return first;
}

9. Polynomial Addition Using Circular Linked List

This program represents three-variable polynomials as circular linked lists, adds two polynomials and evaluates the result.

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

struct polyt
{
    int cf, px, py, pz;
    struct polyt* next;
};

typedef struct polyt* PTR;

PTR insert(PTR poly, int cf, int px, int py, int pz)
{
    PTR cur;
    PTR nn = (PTR)malloc(sizeof(struct polyt));
    nn->cf = cf;
    nn->px = px;
    nn->py = py;
    nn->pz = pz;
    nn->next = NULL;
    cur = poly;
    while (cur->next != poly)
    {
        cur = cur->next;
    }
    cur->next = nn;
    nn->next = poly;
    return poly;
}

void disp(PTR poly)
{
    if (poly->next == poly)
    {
        printf("Polynomial is empty.\n");
        return;
    }
    PTR cur = poly->next;
    do
    {
        printf("%dx^%dy^%dz^%d ", cur->cf, cur->px, cur->py, cur->pz);
        cur = cur->next;
        if (cur != poly)
        {
            printf("+ ");
        }
    } while (cur != poly);
    printf("\n");
}

int evaluate(PTR poly, int x, int y, int z)
{
    int result = 0;
    if (poly->next == poly)
    {
        return result;
    }
    PTR cur = poly->next;
    do
    {
        int termValue = cur->cf;
        termValue *= pow(x, cur->px);
        termValue *= pow(y, cur->py);
        termValue *= pow(z, cur->pz);
        result += termValue;
        cur = cur->next;
    } while (cur != poly);
    return result;
}

bool fmatch(PTR p1, PTR p2)
{
    bool match = true;
    if (p1->px != p2->px)
        match = false;
    if (p1->py != p2->py)
        match = false;
    if (p1->pz != p2->pz)
        match = false;
    return match;
}

PTR add(PTR poly1, PTR poly2, PTR polySum)
{
    PTR cur1 = poly1->next;
    PTR cur2 = poly2->next;
    do
    {
        polySum = insert(polySum, cur1->cf, cur1->px, cur1->py, cur1->pz);
        cur1 = cur1->next;
    } while (cur1 != poly1);
    do
    {
        cur1 = polySum->next;
        bool matchfound = false;
        do
        {
            if (fmatch(cur1, cur2))
            {
                cur1->cf += cur2->cf;
                matchfound = true;
                break;
            }
            cur1 = cur1->next;
        } while (cur1 != polySum);
        if (!matchfound)
        {
            polySum = insert(polySum, cur2->cf, cur2->px, cur2->py, cur2->pz);
        }
        cur2 = cur2->next;
    } while (cur2 != poly2);
    return polySum;
}

int main()
{
    PTR poly1 = (PTR)malloc(sizeof(struct polyt));
    poly1->next = poly1;
    PTR poly2 = (PTR)malloc(sizeof(struct polyt));
    poly2->next = poly2;
    PTR polySum = (PTR)malloc(sizeof(struct polyt));
    polySum->next = polySum;

    poly1 = insert(poly1, 6, 2, 2, 1);
    poly1 = insert(poly1, 4, 0, 1, 5);
    poly1 = insert(poly1, 3, 3, 1, 1);
    poly1 = insert(poly1, 2, 1, 5, 1);
    poly1 = insert(poly1, 2, 1, 1, 3);
    printf("POLY1(x, y, z) = ");
    disp(poly1);

    poly2 = insert(poly2, 1, 1, 1, 1); // Example term
    poly2 = insert(poly2, 4, 3, 1, 1);
    printf("POLY2(x, y, z) = ");
    disp(poly2);

    // Add POLY1(x, y, z) and POLY2(x, y, z) and store the result in POLYSUM(x, y, z)
    polySum = add(poly1, poly2, polySum);

    // Display the sum POLYSUM(x, y, z)
    printf("\nPOLYSUM(x, y, z) = ");
    disp(polySum);

    // Evaluate POLYSUM(x, y, z) for specific values
    int x = 1, y = 2, z = 3;
    int res = evaluate(polySum, x, y, z);
    printf("\nResult of POLYSUM(%d, %d, %d): %d\n", x, y, z, res);

    return 0;
}

10. Binary Search Tree Operations

This program creates a binary search tree of integers and supports inorder, preorder and postorder traversal, as well as search.

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

struct node
{
    int info;
    struct node *lbranch;
    struct node *rbranch;
};

typedef struct node* NODEPTR;

NODEPTR fnGetNode(void);
void fnFreeNode(NODEPTR x);
NODEPTR fnInsertNode(int, NODEPTR);
void fnInOrder(NODEPTR);
void fnPreOrder(NODEPTR);
void fnPostOrder(NODEPTR);
void fnSearchBST(NODEPTR, int);

int main()
{
    NODEPTR root = NULL;
    int iChoice, iItem, i, iNum;

    printf("Create a BST of N Integers \n");
    printf("\nEnter the number N : ");
    scanf("%d", &iNum);
    printf("\nEnter %d numbers\n", iNum);
    for (i = 0; i < iNum; i++)
    {
        scanf("%d", &iItem);
        root = fnInsertNode(iItem, root);
    }

    for (;;)
    {
        printf("\n1.Inorder traversal\n2.Preorder traversal");
        printf("\n3.Postorder traversal\n4.Search\n5.Exit\n");
        printf("\nEnter your choice : ");
        scanf("%d", &iChoice);
        switch (iChoice)
        {
        case 1:
            if (root == NULL)
            {
                printf("\nTree is Empty\n");
            }
            else
            {
                printf("\nInorder Traversal is :\n");
                fnInOrder(root);
                printf("\n");
            }
            break;
        case 2:
            if (root == NULL)
            {
                printf("\nTree is Empty\n");
            }
            else
            {
                printf("\nPreorder Traversal is :\n");
                fnPreOrder(root);
                printf("\n");
            }
            break;
        case 3:
            if (root == NULL)
            {
                printf("\nTree is Empty\n");
            }
            else
            {
                printf("\nPostorder Traversal is :\n");
                fnPostOrder(root);
                printf("\n");
            }
            break;
        case 4:
            printf("\nEnter the element to be searched : ");
            scanf("%d", &iItem);
            fnSearchBST(root, iItem);
            break;
        case 5:
            exit(0);
        default:
            printf("Wrong choice\n");
            break;
        }
    }
    return 0;
}

NODEPTR fnGetNode(void)
{
    NODEPTR x;
    x = (NODEPTR)malloc(sizeof(struct node));
    if (x == NULL)
    {
        printf("\nOut of Memory");
        exit(0);
    }
    return x;
}

void fnFreeNode(NODEPTR x)
{
    free(x);
}

NODEPTR fnInsertNode(int iItem, NODEPTR root)
{
    NODEPTR temp, prev, cur;
    temp = fnGetNode();
    temp->info = iItem;
    temp->lbranch = NULL;
    temp->rbranch = NULL;
    if (root == NULL)
        return temp;
    prev = NULL;
    cur = root;
    while (cur != NULL)
    {
        prev = cur;
        if (iItem == cur->info)
        {
            printf("\nDuplicate items not allowed\n");
            fnFreeNode(temp);
            return root;
        }
        cur = (iItem < cur->info) ? cur->lbranch : cur->rbranch;
    }
    if (iItem < prev->info)
        prev->lbranch = temp;
    else
        prev->rbranch = temp;
    return root;
}

void fnPreOrder(NODEPTR root)
{
    if (root != NULL)
    {
        printf("%d\t", root->info);
        fnPreOrder(root->lbranch);
        fnPreOrder(root->rbranch);
    }
}

void fnInOrder(NODEPTR root)
{
    if (root != NULL)
    {
        fnInOrder(root->lbranch);
        printf("%d\t", root->info);
        fnInOrder(root->rbranch);
    }
}

void fnPostOrder(NODEPTR root)
{
    if (root != NULL)
    {
        fnPostOrder(root->lbranch);
        fnPostOrder(root->rbranch);
        printf("%d\t", root->info);
    }
}

void fnSearchBST(NODEPTR root, int iElem)
{
    if (root != NULL)
    {
        if (iElem < root->info)
            fnSearchBST(root->lbranch, iElem);
        else if (iElem > root->info)
            fnSearchBST(root->rbranch, iElem);
        else
            printf("\n%d is found in the BST\n", iElem);
    }
    else
    {
        printf("\n%d is not found in the BST\n", iElem);
    }
}