WAP for Depth First Binary Tree Search using Recursion

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