---
title: "Data Structures and Algorithms - CSL210"
tags : "SEM4, OC"
---

# Data Structures and Algorithms - CSL210

[e-mail]
9823335046

Classes
Mon - 10am
Sat - 2pm
Thur - 8am

B slot - Exam

Text Books Required

Data Structures and Program Design in C - Robert Kruse

No Hard coding
Save program files as .c files and not .cpp

<limits.h> - `INT_MIN`

# Functions

Name, parameter list, return type, body/defination

Function prototype must be declared

## Recursion

Return address, Local Variable, Parameters, Return Value

Key Notes
- Base Case
- Making sure you are dealing with progressively smaller or simplers sub problems
- How to parameterize the function is an important aspect

Recursion vs Iteration

Iteration is faster as it doesn't increase the stack space (overhead) and needs to store the activation record at each call

### Tail Recursion

When the recursion calling statement is the last statement

Stacks (All local variables, parameters, etc) overwrite themselves so the stack size does not increase with the number of recursive calls

In this case iteration and recursion achieve the same level of effeiciency

Modern computers do this optimization on their own, so tail recursion turns into iterative

1) Interative or Tail Recursive
2) Now tail recursive and dubplication of task -> accumulators
3) Otherwise recursion

# Binary Search and Variation

## Binary Search - Iterative

#include <stdio.h>

//Binary Search

int BinSearch(int arr[], int n, int x);

int main()
{
    int arr[] = {1,2,3,4,5};
    int n = *(&arr + 1) - arr;
    int x = 3;
    
    printf("Index - %d", BinSearch(arr, n, x));
    
    return 0;
}

int BinSearch(int arr[], int n, int x)
{
    int retval = -1;
    int left = 0;
    int right = n;
    int found = 0;
    while ((right >= left) && (!found))
    {
        int mid = (right+left)/2;
        if (x == arr[mid])
        {
            retval = mid;
            found = 1;
        }
        else
        {
            if (x < arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return retval;
}

## Binary Search using Recurrsive Function

int RecurBinSearch(int arr[], int left, int right, int x)
{
    int retval;
    if (right < left)
        retval = -1;
    else
    {
        int mid = (right+left)/2;
        if (x == arr[mid])
            retval = mid;
        else
            if (x < arr[mid])
                retval = RecurBinSearch(arr, left, mid - 1, x);
            else
                retval = RecurBinSearch(arr, mid + 1, right, x);
    }
    return retval;
}

## Binary Search - Iterative, Almost Sorted Array Function
(issue)

int BinSearch(int arr[], int n, int x)
{
    int retval = -1;
    int right = n, left = 0;
    int found = 0;
    while ((right >= left) && (!found))
    {
        int mid = (right+left)/2;
        if (x == arr[mid])
        {
            retval =  mid;
            found = 1;
        }
        else if ((mid - 1 >= left) && (arr[mid - 1] == x))
        {
            retval = (mid - 1);
            found = 1;
        }
        else if ((mid + 1 <= right) && (arr[mid + 1] == x))
        {
            retval =  mid + 1;
            found = 1;
        }
        else
            if (x < arr[mid])
                right = mid - 2;
            else
                left = mid + 2;
    }
    return retval;
}

## Binary Search - Recursive, Almost sorted array Function

int RecurBinSearch(int arr[], int left, int right, int x)
{
    int retval;
    if (right < left)
        retval =  -1;
    else
    {
        int mid = (right+left)/2;
        if (x == arr[mid])
            retval =  mid;
        else
        {
            if ((mid - 1 >= left) && (arr[mid - 1] == x))
                retval = (mid-1);
            else
            {
                if ((mid + 1 <= right) && arr[mid + 1] == x)
                    retval =  mid+1;
                else
                    if (x < arr[mid])
                        retval = RecurBinSearch(arr, left, mid - 2, x);
                    else
                        retval = RecurBinSearch(arr, mid + 2, right, x);
            }
        }
    }
    return retval;
}

# Sorting Techniques

## Bubble Sort

void BubSort(int arr[], int n)
{
    int i = 0;
    int swap = 1;
    while ((i < n-1) && swap)
    {
        swap = 0;
        for (int j = 0; j < n-i-1; j++)
            if (arr[j]>arr[j+1])
            {
                arr[j] += arr[j+1];
                arr[j+1] = arr[j] - arr[j+1];
                arr[j] = arr[j] - arr[j+1];
                swap = 1;
            }
    }
}

Working -

6 1 4 5 2 3 //Input array
1 6 4 5 2 3
1 4 6 5 2 3
1 4 5 6 2 3
1 4 5 2 6 3
1 4 5 2 3 6 //End of first iteration (5 comparisons)
1 4 5 2 3 6 
1 4 5 2 3 6
1 4 2 5 3 6
1 4 2 3 5 6 //End of second iteration (4 comparisions)
...

Flag - used to avoid unnecessary iterations

Number of steps at max will be $\frac{n(n+1)}{2}$

Time Complexity = O(n^2^)

Requires 2 loop

## Selection Sort

void SelSort(int arr[], int n)
{
    int i = 0;
    for (i = 0; i < n-1; i++)
    {
        int min = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min])
                min = j;
        if (i!=min)
        {
            arr[i] += arr[min];
            arr[min] = arr[i] - arr[min];
            arr[i] = arr[i] - arr[min];
        }
    }
}

Though the time complexity of both Bubble sort and selection sort is the same, the swapping of elements is dont more effciently in Selection Sort compared to Bubble Sort

## Insertion sort

void InsSort(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i-1;
        while((j >= 0) && (arr[j]>key))
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Working -

7 5 1 2 4 6 8 3 //Input array
7 5 1 2 4 6 8 3 //Key = 7, already sorted can be skipped
5 7 1 2 4 6 8 3 //Key = 5
1 5 7 2 4 6 8 3 //Key = 1, the array before the next key is completely sorted
1 2 5 7 4 6 8 3 //Key = 2
1 2 4 5 7 6 8 3 //Key = 4
1 2 4 5 6 7 8 3 //Key = 6
1 2 4 5 6 7 8 3 //Key = 8
1 2 3 4 5 6 7 8 //Key = 3

## Quick Sort

Select a pivot and partition the array keeping greater elements on one side and smaller in on the other, and calling this function recursively

Time Complexity - O(nlog n)
Space Complexity - O(n)

Inplace Sorter

Preferable for sorting Arrays over Merge Sort vice versa for linked list

void QukSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int part = split(arr, left, right);
        if (part >= 0)
        {
            QukSort(arr, left, part);
            QukSort(arr, part+1, right);
        }
    }
}

int split(int arr[], int left, int right)
{
    int retval = -1;
    if (left < right)
    {
        int pivot = left;
        int i = left;
        int j = right;
        while (i < j)
        {
            while ((arr[i] < arr[pivot]) && (i < right))
            {
                i++;
            }
            while ((arr[j] > arr[pivot]) && (j > 0))
            {
                j--;
            }
            if (i < j)
            {
                arr[i] = arr[j] + arr[i];
                arr[j] = arr[i] - arr[j];
                arr[i] = arr[i] - arr[j];
            }
        }
        retval = j;
    }
    return retval;
}

## Merge Sort

Merge Sort involves dividing the array into smaller portions and then merging two arrays at a time in a sorted manner

Time Complexity - O(nlog n)
Space Complexity - O(n)

Not inplace sort

Recursive Merging of sorted arrays

void merge_sort(int arr[], int temp[], int start, int end)
{
    int arr_size = end - start;
    if (arr_size == 2)
    {
        if (arr[start] > arr[start + 1])
        {
            int hold = arr[start];
            arr[start] = arr[start + 1];
            arr[start + 1] = hold;
        }
    }
    else if ((arr_size != 1) && (arr_size != 0))
    {
        int mid = (end + start)/2;
        merge_sort(arr, temp, start, mid);
        merge_sort(arr, temp, mid, end);
        int i = start;
        int j = mid;
        int k = start;
        while ((i < mid) && (j < end))
        {
            if (arr[i]>arr[j])
            {
                temp[k] = arr[j];
                j++;
            }
            else
            {
                temp[k] = arr[i];
                i++;
            }
            k++;
        }
        while (i < mid)
        {
            temp[k] = arr[i];
            i++;
            k++;
        }
        while(j < end)
        {
            temp[k] = arr[j];
            j++;
            k++;
        }
        for (i = start; i < end; i++)
        {
            arr[i] = temp[i];
        }
    }
}

Counting number of Inversions

int merge_sort(int arr[], int temp[], int start, int end)
{
    int ret_val = 0;
    int arr_size = end - start;
    //printf("%d, %d\n", start, end);
    if (arr_size == 1)
        ret_val = 0;
    else if (arr_size == 0)
        ret_val = 0;
    else if (arr_size == 2)
    {
        if (arr[start] > arr[start + 1])
        {
            ret_val = 1;
            //printf("%d, %d\n", arr[start], arr[start + 1]);
            int hold = arr[start];
            arr[start] = arr[start + 1];
            arr[start + 1] = hold;
        }
        else
            ret_val = 0;
    }
    else
    {
        int mid = (end + start)/2;
        //printf("%d", mid);
        ret_val = merge_sort(arr, temp, start, mid) + merge_sort(arr, temp, mid, end);
        int i = start;
        int j = mid;
        int k = start;
        while ((i < mid) && (j < end))
        {
            if (arr[i]>arr[j])
            {
                //printf("%d, %d\n", arr[i], arr[j]);
                ret_val = ret_val + (mid - i);
                temp[k] = arr[j];
                j++;
            }
            else
            {
                temp[k] = arr[i];
                i++;
            }
            k++;
        }
        while (i < mid)
        {
            temp[k] = arr[i];
            i++;
            k++;
        }
        while(j < end)
        {
            temp[k] = arr[j];
            j++;
            k++;
        }
        for (i = start; i < end; i++)
        {
            arr[i] = temp[i];
        }
    }
    return ret_val;
}

## Heap Sort

Insertion Sort
- O(n^2^)
- Sorts in place

Merge Sort
- O(nlog n)
- Takes extra memory

Heap Sort
- O(nlog n)
- Sorts in place

Heap can mean
- A data structure
- Memory Area (garbage collection)

Heap sort refers to Data Structure heap

A heap is alist in which each entry contains a key, and, for all positions k in the list, the key at position is at least as large as the keys in positions 2k and 2k+1, provided these positions exist in the list

The binary heap is a data structure that is an array object which we can view as a merely complete binary tree

Array A which represents a heap has 2 attributes
- A.length - Length of Array
- A.heapsize - how many elements in the heap are stored within array A

A[1...A.length] - may contain numbers
A[1...A.heapsize] - Valid numbers

$0 \leq \text{A.heapsize} \leq \text{A.length}$

parent(i)
    return [i/2]
left(i)
    return 2i
right(i)
    reuturn 2i+1

int left(int k)
{
    return ((2*k) + 1);
}

int right(int k)
{
    return ((2*k) + 2);
}

void max_heap(int arr[], int n, int i)
{
    int largest = i;
    int l = left(i);
    int r = right(i);
    
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    
    if (largest != i)
    {
        arr[i] += arr[largest];
        arr[largest] = arr[i] - arr[largest];
        arr[i] = arr[i] - arr[largest];
        max_heap(arr, n, largest);
    }
}

# Pointers

Pointers hold the address of variables

& - Referencing Operator

Pointer takes the same amount of memory

The parameter passing mechanism in C language is pass by value except for arrays

Arrays are passed by reference

## Pointer Operations

- Variable which contains the address of another variable

`int *p`
Here we can say
- `p` is a pointer to an integer
- `*p` is an integer

`*` - dereferencing operator

All pointers require the same amount of memory

`&` - Referencing operator

Valid
- Assignment of poinsters of the same type
- Adding or subtracting a pointer and an integer
- Assignming and comparing to zero
- Subtracting two pointers
- Comparing two pointers

Invalid
- Adding 2 pointers
- Multiply
- Divide
- Shift
- Mask
- Add a float or double to a pointer
- Assign one pointer to another type without a cast

Array of strings

void print(char* C)
{
    while (*C != '\0')
        printf("%c", (*C++));
    printf("\n");
}

void check(char *C[SIZE], int i)
{
    printf("%s", C[i]);
}

int main()
{
    char *C[] = {"Hi", "Hello", "Apple", "Bottle"};
    int n = sizeof(C)/sizeof(C[0]);
    int i = 0, j = 0 ;
    printf("%c\n\n", *(*(C+i)+j));
    print(*(C+1));
    check(C, 3);

    return 0;
}

# Stack

FILO

Basic Stack Requirements

typedef int stack_entry_type;

typedef struct stack
{
    stack_entry_type list[SIZE];
    int top;
}STACK;

void InitStack(STACK *s)
{
    s->top = -1;
}

int IsStackFull(STACK s)
{
    return (s.top == SIZE - 1);
}

int IsStackEmpty(STACK s)
{
    return (s.top == -1);
}

void push(stack_entry_type ent, STACK *s)
{
    if(!IsStackFull(*s))
    {
        s->list[(s->top) + 1] = ent;
        s->top = s->top + 1;
    }
}

stack_entry_type pop(STACK *s)
{
    stack_entry_type ent;
    if (!IsStackEmpty(*s))
    {
        ent = s->list[s->top];
        s->top = s->top - 1;
    }
    else
        ent = '\0';
    return ent;
}

# Queue

FIFO
dequeue operation - Removing
enqueue operation - Adding

typedef int queue_entry_type;

typedef struct queue
{
    queue_entry_type list[SIZE];
    int front;
    int rear;
    int count;
}QUEUE;

void InitQueue(QUEUE *q)
{
    q->front = 0;
    q->rear = -1;
    q->count = 0;
}

int IsQueueFull(QUEUE q)
{
    return (q.count >= SIZE);
}

int IsQueueEmpty(QUEUE q)
{
    return (q.count == 0);
}

int QueueSize(QUEUE q)
{
    return q.count;
}

int enqueue(queue_entry_type ent, QUEUE *q)
{
    int retval = 1;
    if(!IsQueueFull(*q))
    {
        q->count++;
        q->rear = (q->rear+1)%SIZE;
        q->list[q->rear] = ent;
    }
    else
    {
        retval = 0;
        printf("Queue is Full");
    }
    return retval;
}

void clearQueue(QUEUE *q)
{
    q->count = 0;
    q->front = q->rear + 1;
}

int dequeue(QUEUE *q)
{
    queue_entry_type ent = -1;
    if (!IsQueueEmpty(*q))
    {
        q->count--;
        ent = q->list[q->front];
        q->front = (q->front + 1)%SIZE;
    }
    else
        printf("Queue is Empty");
    return ent;
}

void traverseQueue(QUEUE q)
{
    int i;
    printf("\n");
    if (!IsQueueEmpty(q))
        for (i = q.front; i-q.front < q.count; i++)
            printf("  %d", q.list[i%SIZE]);
    else
        printf("\nQueue is empty");
}

queue_entry_type QueueFront(QUEUE q)
{
    return q.front;
}

# Linked List

Arrays are suitable for -
- Inserting/Deleting an element at the end
- Randomely accessing any element
- Searching the list for a particular value

Linked Lists are suitable for -
- Inserting an element
- Deleting an element
- Applications where sequential access is required
- In situations where the number of elements cannot be predicted beforehand

Types of linked lists (Links)
- Linear Single-Linked List
- Circular Linked List
- Doubly Linked List

## List Basic

typedef int listentry;

typedef struct node
{
    listentry entry;
    struct node *next;
}NODE;

### Create Node

NODE * CreateNode(listentry ent)
{
    NODE *p;
    p = (NODE *)malloc(sizeof(NODE));
    p->entry = ent;
    p->next = NULL;
    return p;
}

### Insert Node at Begining

NODE * InsertBegin(NODE *header, listentry ent)
{
    NODE *p;
    p = CreateNode(ent);
    if (header == NULL)
        header = p;
    else
    {
        p->next = header;
        header = p;
    }
    return header;
}

### Insert Node at End

NODE * InsertEnd(NODE * header, listentry ent)
{
    NODE *p, *curr;
    p = CreateNode(ent);
    if (header == NULL)
        header = p;
    else
    {
        curr = header;
        while (curr->next != NULL)
        {
            curr = curr->next;
        }
        curr->next = p;
    }
    return header;
}

### Insert At

NODE* InsertAt(NODE* header, listentry ent, int pos)
{
    NODE* p;
    p = CreateNode(ent);
    if (header == NULL)
        if (pos > 0)
            printf("\nThe List is smaller than the mentioned position\n");
        else
            header = p;
    else
    {
        if (pos == 0)
        {
            p->next = header;
            header = p;
        }
        else
        {
            NODE* curr = header;
            int i = 1;
            while((i < pos)&&(curr != NULL))
            {
                curr = curr->next;
                i++;
            }
            if (curr != NULL)
            {
                p->next = curr->next;
                curr->next = p;
            }
            else
                printf("\nThe List is smaller than the mesntioned position\n");
        }
    }
    return header;
}

### Remove Node

void RemoveNode(NODE* header, int nn)
{
    NODE* curr = header;
    if (nn == 0)
    {
        *header = *curr->next;
    }
    else
    {
        for (int i = 0; i < nn-1; i++)
        {
            curr = curr->next;
            if (curr == NULL)
            {
                i = nn;
                printf("\nERROR - Position larger than list size\n\n");
            }
        }
        if (curr != NULL)
        {
            NODE* del_node = curr->next;
            curr->next = del_node->next;
            free(del_node);
        }
    }

### Print List

void printlist(NODE* header)
{
    if (header == NULL)
        printf("Empty List");
    else
    {
        while (header != NULL)
        {
            printf("   %d ->", header->entry);
            header = header->next;
        }
        printf("   NULL\n");
    }
}

### Length of List

int length(NODE* header)
{
    int i = 0;
    while (header != NULL)
    {
        i++;
        header = header->next;
    }
    return i;
}

### Reverse List

NODE* Reverse(NODE* header)
{
    NODE *prev, *curr, *next;
    if (header != NULL)
    {
        curr = header;
        prev = NULL;
        next = curr->next;
        while(curr != NULL)
        {
            curr->next = prev;
            prev = curr;
            curr = next;
            if (curr != NULL)
            {
                next = curr->next;
            }
        }
        header = prev;
    }
    return header;
}

### List as Stack

NODE *Stack_PUSH(NODE* header, listentry ent)
{
    return (InsertBegin(header, ent));
}

NODE* Stack_POP(NODE* header, listentry* out)
{
    NODE *p;
    *out = -1;
    if (header == NULL)
        printf("NULL - Popping an empty Stack\n");
    else
    {
        p = header;
        header = header->next;
        *out = p->entry;
        //printlist(header);
        free(p);
    }
    return header;
}

int main()
{
    NODE *Stack = NULL;
    for (int i = 0; i < 10; i++)
        Stack = Stack_PUSH(Stack, i);
    printlist(Stack);
    listentry a = 0;
    for (int i = 0; i < 11; i++)
    {
        Stack = Stack_POP(Stack, &a);
        printf("Popped element - %d\n", a);
    }

    return 0;
}

Alternate

typedef int listentry;
typedef int BOOL;

typedef struct node
{
    listentry entry;
    struct node *next;
}NODE;

typedef struct List_Stack
{
    NODE *top;
}ListStack;

void Stack_INIT(ListStack *stack)
{
    stack->top = NULL;
}

BOOL Stack_EMPTY(ListStack *stack)
{
    BOOL ret = 0;
    if (stack->top == NULL)
        ret = 1;
    return ret;
}
void Stack_PUSH(ListStack* stack, listentry ent)
{
    NODE* p;
    p = (NODE*)malloc(sizeof(NODE));
    if (p == NULL)
        printf("Exhausted Memory\n");
    else
    {
        p->entry = ent;
        p->next = stack->top;
        stack->top = p;
    }
}

listentry Stack_POP(ListStack* stack)
{
    NODE *p;
    listentry ret = -1;
    if (stack->top == NULL)
        printf("NULL - Popping an empty Stack\n");
    else
    {
        p = stack->top;
        stack->top = p->next;
        ret = p->entry;
        free(p);
    }
    return ret;
}

### List as Queue

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

typedef int listentry;
typedef int BOOL;

typedef struct node
{
    listentry entry;
    struct node *next;
}NODE;

NODE * CreateNode(listentry ent)
{
    NODE *p;
    p = (NODE *)malloc(sizeof(NODE));
    p->entry = ent;
    p->next = NULL;
    return p;
}

NODE * InsertBegin(NODE *header, listentry ent)
{
    NODE *p;
    p = CreateNode(ent);
    if (header == NULL)
        header = p;
    else
    {
        p->next = header;
        header = p;
    }
    return header;
}

void RemoveNode(NODE* header, int nn)
{
    NODE* curr = header;
    if (nn == 0)
    {
        if (header != NULL)
            curr = header;
            header = NULL;
            free(curr);
    }
    else
    {
        for (int i = 0; i < nn-1; i++)
        {
            curr = curr->next;
            if (curr == NULL)
            {
                i = nn;
                printf("\nERROR - Position larger than list size\n\n");
            }
        }
        if (curr != NULL)
        {
            NODE* del_node = curr->next;
            curr->next = del_node->next;
            free(del_node);
        }
    }
}

NODE* Queue_ENQUEUE(NODE* queue, listentry ent)
{
    return InsertBegin(queue, ent);
}

BOOL Queue_EMPTY(NODE* queue)
{
    BOOL ret = 0;
    if (queue == NULL)
        ret = 1;
    return ret;
}

listentry Queue_DEQUEUE(NODE* queue)
{
    listentry ret = -1;
    printf("\n%d", Queue_EMPTY(queue));
    if (Queue_EMPTY(queue))
        printf("ERROR - Popping an Empty Queue");
    else
    {
        NODE* curr = queue;
        int n = 0;
        while (curr->next != NULL)
        {
            curr = curr->next;
            n++;
        }
        ret = curr->entry;
        RemoveNode(queue, n);
        printf(" Hi ");
    }
    return ret;
}

void printlist(NODE* header)
{
    if (header == NULL)
        printf("Empty List");
    else
    {
        while (header != NULL)
        {
            printf("   %d ->", header->entry);
            header = header->next;
        }
        printf("   NULL\n");
    }
}

int main()
{
    NODE *Queue;
    for (int i = 0; i < 10; i++)
    {
        Queue = Queue_ENQUEUE(Queue, i);
        printlist(Queue);
    }
    for (int i = 0; i < 11; i++)
    {
        printf("Popped element - %d\n", Queue_DEQUEUE(Queue));
        //RemoveNode(Queue, 0);
        printlist(Queue);
    }
    RemoveNode(Queue, 0);
    printlist(Queue);
    printf("\n\n%d", Queue_EMPTY(Queue));
    

    return 0;
}

# Binary Tree

At any level i maximum number of nodes is 2^i^

Total number of nodes in a full tree with height h, n = 2^h^-1
h = log(n+1)
- h determines the running time

## Search

Start at root and search the tree level by level until you find the number - O(n)

Binary Search Tree
- The value stored at a node is greater than the value stored at its left child and less than the value stored at the right child

This property causes the Time complexity to be O(log n)

### Traversal

Preorder - Root L~c~ R~c~
Inorder - L~c~ Root R~C~
Postorder - L~c~ R~c~ Root


- Inorder Traversal - AEHJMTY
- Preorder Traversal - JEAHTMY
- Postorder Traversal - AHEMYTJ



Basics

typedef int BOOL;
typedef int key_type;
typedef char info_type;

typedef struct node
{
  info_type data;
  struct node *left;
  struct node *right;
}NODE;

NODE *NewNode (int data)
{
  NODE *node = (NODE *) malloc (sizeof (NODE));
  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

Printing

void PrintPostorder(NODE* node)
{
    if (node == NULL)
        return;
    PrintPostorder(node->left);
    PrintPostorder(node->right);
    printf("%d ", node->data);
}
void PrintInorder(NODE* node)
{
    if (node == NULL)
        return;
    PrintPostorder(node->left);
    printf("%d ", node->data);
    PrintPostorder(node->right);
}
void PrintPreorder(NODE* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    PrintPostorder(node->left);
    PrintPostorder(node->right);
}

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

typedef int BOOL;
typedef int key_type;
typedef char info_type;

typedef struct item_tag
{
    key_type key;
    info_type info;
}Item_type;

typedef struct Tree_node_tag
{
    Item_type item;
    struct Tree_node_tag *left;
    struct Tree_node_tag *right;
}Tree_Node_type;

typedef struct Tree_Tag
{
Tree_Node_type *root;
}Tree_type;

void tree_INIT(Tree_type *tree)
{
    tree->root = NULL;
}

BOOL tree_EMPTY(Tree_type *root)
{
    BOOL ret = 0;
    if (root == NULL)
        ret = 1;
    return ret;
}

int getLeafCount(Tree_Node_type *root)
{
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        if(root->left == NULL && root->right==NULL)
        {
                return 1;
        }
        else
        {
            return ((getLeafCount(root->left)) + (getLeafCount(root->right)));
        }
    }
}

void Visit(Tree_Node_type *root)
{
    printf("\n %d %c", root->item.key, root->item.info);
}

Tree_Node_type * Treesearch(Tree_Node_type *root, key_type target)
{
    Tree_Node_type *temp = NULL;
    if (root != NULL)
    {
        if(target == root->item.key)
        {
            temp = root;
            //return(root) ;
        }
        else
        {
            if (target < root->item.key)
            {
                temp = Treesearch(root->left, target);
            }
            else
            {
                temp = Treesearch(root->right, target);
            }
        }
    }
    else
    {
        temp = NULL;
    }
    return(temp);
}

Tree_Node_type * insert(Tree_Node_type *root, Item_type item)
{
    Tree_Node_type *p;
    p = (Tree_Node_type *) malloc(sizeof(Tree_Node_type));
    if(p == NULL)
    {
        printf("Malloc not successful");
        printf("Exhausted Memory\n");
    }
    else
    {
        p->item = item;
        p->right = NULL;
        p->left = NULL;
        if (root == NULL)
        {
            root = p;
        }
        else
        {
            if(p->item.key < root->item.key)
            {
                root->left = insert(root->left, p->item);
            }
            else
            {
                root->right = insert(root->right, p->item);
            }
        }
    }
    return root;
}
int main()
{
    Tree_Node_type *tree;
    for (Item_type i = 0; i < 10; i++)
        insert(tree, i);

    return 0;
}