Q:

Write a C Program for Depth First Search using Recursion

robaa
Save to bookmark
|
2022-11-25
|
  151 
0

Write a C Program for Depth First Search using Recursion. Here’s simple Program for Depth First Search using Recursion in C Programming Language.

C programming, examples, C programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-25
need an explanation for this answer? contact us directly to get an explanation for this answer

Depth First Search : :

  • Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure 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.
  • Conditions: 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.

Here is the source code of the C Program for Depth First Search using Recursion. The C Program is successfully compiled and run on a Windows system. The program output is also shown below.

 
 

SOURCE CODE : :

/*  C Program for Depth First Search using Recursion */

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

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

void generate(struct node **, int);
void DFS(struct node *);
void delete(struct node **);

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

    do
    {
        printf("\nEnter your choice:\n1. Insert\n2. Perform DFS Traversal\n3. Exit\n\nChoice: ");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1:
            printf("\nEnter 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 (choice != 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)->a = num;
        (*head)->left = (*head)->right = NULL;
    }
    else
    {
        while (temp != NULL)
        {
            if (num > temp->a)
            {
                prev = temp;
                temp = temp->right;
            }
            else
            {
                prev = temp;
                temp = temp->left;
            }
        }
        temp = (struct node *)malloc(sizeof(struct node));
        temp->a = num;
        if (num >= prev->a)
        {
            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->a);
    }
}

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

Output : :

/* C Program for Depth First Search using Recursion  */

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

Above is the source code for C Program for Depth First Search using Recursion which is successfully compiled and run on Windows System.The Output of the program is shown above .

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C Recursion Solved Programs – C Programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C Program to Traverse Binary Tree using Recursion... >>
<< C program to check number is palindrome or not usi...