DFS Traversal of a Tree Without using Recursion in C

The following C program, using iteration, 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 root 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 iteratively. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program for Depth First Binary Tree Search without using 
  3.  * Recursion
  4.  */
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7.  
  8. struct node
  9. {
  10.     int a;
  11.     struct node *left;
  12.     struct node *right;
  13.     int visited;
  14. };
  15.  
  16. void generate(struct node **, int);
  17. void DFS(struct node *);
  18. void delete(struct node **);
  19.  
  20. int main()
  21. {
  22.     struct node *head = NULL;
  23.     int choice = 0, num, flag = 0, key;
  24.  
  25.     do
  26.     {
  27.         printf("\nEnter your choice:\n1. Insert\n2. Perform DFS Traversal\n3. Exit\nChoice: ");
  28.         scanf("%d", &choice);
  29.         switch(choice)
  30.         {
  31.         case 1: 
  32.             printf("Enter element to insert: ");
  33.             scanf("%d", &num);
  34.             generate(&head, num);
  35.             break;
  36.         case 2: 
  37.             DFS(head);
  38.             break;
  39.         case 3: 
  40.             delete(&head);
  41.             printf("Memory Cleared\nPROGRAM TERMINATED\n");
  42.             break;
  43.         default: 
  44.             printf("Not a valid input, try again\n");
  45.         }
  46.     } while (choice != 3);
  47.  
  48.     return 0;
  49. }
  50.  
  51. void generate(struct node **head, int num)
  52. {
  53.     struct node *temp = *head, *prev = *head;
  54.  
  55.     if (*head == NULL)
  56.     {
  57.         *head = (struct node *)malloc(sizeof(struct node));
  58.         (*head)->a = num;
  59.         (*head)->visited = 0;
  60.         (*head)->left = (*head)->right = NULL;
  61.     }
  62.     else
  63.     {
  64.         while (temp != NULL)
  65.         {
  66.             if (num > temp->a)
  67.             {
  68.                 prev = temp;
  69.                 temp = temp->right;
  70.             }
  71.             else
  72.             {
  73.                 prev = temp;
  74.                 temp = temp->left;
  75.             }
  76.         }
  77.         temp = (struct node *)malloc(sizeof(struct node));
  78.         temp->a = num;
  79.         temp->visited = 0;
  80.         if (temp->a >= prev->a)
  81.         {
  82.             prev->right = temp;
  83.         }
  84.         else
  85.         {
  86.             prev->left = temp;
  87.         }
  88.     }
  89. }
  90.  
  91. void DFS(struct node *head)
  92. {
  93.     struct node *temp = head, *prev;
  94.  
  95.     printf("On DFS traversal we get:\n");
  96.     while (temp && !temp->visited)
  97.     {
  98.         if (temp->left && !temp->left->visited)
  99.         {
  100.             temp = temp->left;
  101.         }
  102.         else if (temp->right && !temp->right->visited)
  103.         {
  104.             temp = temp->right;
  105.         }
  106.         else
  107.         {
  108.             printf("%d  ", temp->a);
  109.             temp->visited = 1;
  110.             temp = head;
  111.         }
  112.     }
  113. }
  114.  
  115. void delete(struct node **head)
  116. {
  117.     if (*head != NULL)
  118.     {
  119.         if ((*head)->left)
  120.         {
  121.             delete(&(*head)->left);
  122.         }
  123.         if ((*head)->right)
  124.         {
  125.             delete(&(*head)->right);
  126.         }
  127.         free(*head);
  128.     }
  129. }

$ cc pgm33.c
$ a.out
 
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: 2
 
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: 1
 
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: 6
 
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: 2
On DFS traversal we get:
1  2  4  3  6  8  7  5  
 
Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 3
Memory Cleared
PROGRAM TERMINATED

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Trees, go to Trees. If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.