A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

C program for Depth First Binary Tree search using Recursion


Problem Description


The following C program use Recursion to perform a Depth First Search traversal. Depth-first search (DFS) is an algorithm for traversing or searching a tree or graph. The concept of backtracking is used in DFS. In this program we are performing DFS on a binary tree. In DFS, the deepest and univisited node is visited and backtracks to it’s parent node if no siblings of that node exists.
The DFS works on acyclic graph. DFS may fail if it enters a cycle. Care must be taken by not extending a path to a node if it already has.


C program for Depth First Binary Tree search using Recursion - Source code
     
                
  /*
 * C Program for Depth First Binary Tree Search using Recursion
 */
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int n;
    struct node *left;
    struct node *right;
};

void generate_tree(struct node **, int);
void perform_DFS(struct node *);
void delete(struct node **);

int main()
{
    struct node *head = NULL;
    int c = 0, num, flag = 0, key;

    do
    {
        printf("\nEnter your choice:\n1. Insert\n2. Perform DFS Traversal\n3. Exit\nChoice: ");
        scanf("%d", &c);
        switch(c)
        {
        case 1:
            printf("Enter element to insert: ");
            scanf("%d", &num);
            generate(&head, num);
            break;
        case 2:
            DFS(head);
            break;
        case 3:
            delete(&head);
            printf("Memory Cleared\nPROGRAM TERMINATED\n");
            break;
        default:
            printf("Not a valid input, try again\n");
        }
    } while (c != 3);
    return 0;
}

void generate(struct node **head, int num)
{
    struct node *temp = *head, *prev = *head;

    if (*head == NULL)
    {
        *head = (struct node *)malloc(sizeof(struct node));
        (*head)->n = num;
        (*head)->left = (*head)->right = NULL;
    }
    else
    {
        while (temp != NULL)
        {
            if (num > temp->n)
            {
                prev = temp;
                temp = temp->right;
            }
            else
            {
                prev = temp;
                temp = temp->left;
            }
        }
        temp = (struct node *)malloc(sizeof(struct node));
        temp->n = num;
        if (num >= prev->n)
        {
            prev->right = temp;
        }
        else
        {
            prev->left = temp;
        }
    }
}

void DFS(struct node *head)
{
    if (head)
    {
        if (head->left)
        {
            DFS(head->left);
        }
        if (head->right)
        {
            DFS(head->right);
        }
        printf("%d  ", head->n);
    }
}

void delete(struct node **head)
{
    if (*head != NULL)
    {
        if ((*head)->left)
        {
            delete(&(*head)->left);
        }
        if ((*head)->right)
        {
            delete(&(*head)->right);
        }
        free(*head);
    }
}

     
      

Program Output


Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 5
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 3
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 4
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 2
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 7
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 8
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 6
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 2
2  4  3  6  8  7  5  
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 3