C Programming Code Examples C > Recursion Code Examples C Program for Depth First Binary Tree Search using Recursion C Program 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. #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, j, 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", &j); generate(&head, j); 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 j) { struct node *temp = *head, *prev = *head; if (*head == NULL) { *head = (struct node *)malloc(sizeof(struct node)); (*head)->a = j; (*head)->left = (*head)->right = NULL; } else { while (temp != NULL) { if (j > temp->a) { prev = temp; temp = temp->right; } else { prev = temp; temp = temp->left; } } temp = (struct node *)malloc(sizeof(struct node)); temp->a = j; if (j >= 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); } }