The following C program, using recursion, performs a Depth First Search traversal. 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 to apply DFS on a binary tree recursively. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#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\nChoice: "); scanf("%d", &choice); switch(choice) { 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 (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
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 Memory Cleared PROGRAM TERMINATED