Question

1. Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal of the tree.

50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5

1. Write an algorithm to delete a node in Singly Linked List                            [12
2. Write an algorithm of Binary Search                                                              [10]
3. Write a program in ‘C’ to generate Fibonacci series using recursion            [8]

Answer 1

*** FUNCTION TO DELETE A NODE FROM SINGLE LINK LIST:-

/* Given a reference (pointer to pointer) to the head of a list

   and a key, deletes the first occurrence of key in linked list */

void deleteNode(struct Node **head_ref, int key)

{

    // Store head node

    struct Node* temp = *head_ref, *prev;

  

    // If head node itself holds the key to be deleted

    if (temp != NULL && temp->data == key)

    {

        *head_ref = temp->next;   // Changed head

   free(temp);               // free old head

        return;

    }

  

    // Search for the key to be deleted, keep track of the

    // previous node as we need to change 'prev->next'

    while (temp != NULL && temp->data != key)

    {

        prev = temp;

        temp = temp->next;

    }

  

    // If key was not present in linked list

    if (temp == NULL) return;

  

    // Unlink the node from linked list

    prev->next = temp->next;

  

    free(temp); // Free memory

}

B. ALGORITHM FOR BINARY SEARCH:-

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

C.Fibonacci Series using recursion in C:-

1. #include<stdio.h>    
2. void printFibonacci(int n){    
3.     static int n1=0,n2=1,n3;    
4.     if(n>0){    
5.          n3 = n1 + n2;    
6.          n1 = n2;    
7.          n2 = n3;    
8.          printf("%d ",n3);    
9.          printFibonacci(n-1);    
10.     }    
11. }    
12. int main(){    
13.     int n;    
14.     printf("Enter the number of elements: ");    
15.     scanf("%d",&n);    
16.     printf("Fibonacci Series: ");    
17.     printf("%d %d ",0,1);    
18.     printFibonacci(n-2); //n-2 because 2 numbers are already printed    
19.   return 0;  
20. }    

OUTPUT:-

Enter the number of elements:15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377