C Program to Traverse the Tree without Recursion

The following C program, using iteration, searches for a given node in a tree. The tree we have used is the binary search tree. A binary search tree follows a concept of the nodes whose numbers are lesser than the parent/pointed node are linked to the left and the nodes whose are greater than the parent/pointed node are linked to the right.

Here is the source code of the C program to search for an element in a 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 to Traverse the Tree Non-Recursively
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. struct node
  8. {
  9.     int a;
  10.     struct node *left;
  11.     struct node *right;
  12. };
  13.  
  14. void generate(struct node **, int);
  15. int search(struct node *, int);
  16. void delete(struct node **);
  17.  
  18. int main()
  19. {
  20.     struct node *head = NULL;
  21.     int choice = 0, num, flag = 0, key;
  22.  
  23.     do
  24.     {
  25.         printf("\nEnter your choice:\n1. Insert\n2. Search\n3. Exit\nChoice: ");
  26.         scanf("%d", &choice);
  27.         switch(choice)
  28.         {
  29.         case 1: 
  30.             printf("Enter element to insert: ");
  31.             scanf("%d", &num);
  32.             generate(&head, num);
  33.             break;
  34.         case 2: 
  35.             printf("Enter key to search: ");
  36.             scanf("%d", &key);
  37.             flag = search(head, key);
  38.             if (flag)
  39.             {
  40.                 printf("Key found in tree\n");
  41.             }
  42.             else
  43.             {
  44.                 printf("Key not found\n");
  45.             }
  46.             break;
  47.         case 3: 
  48.             delete(&head);
  49.             printf("Memory Cleared\nPROGRAM TERMINATED\n");
  50.             break;
  51.         default: printf("Not a valid input, try again\n");
  52.         }
  53.     } while (choice != 3);
  54.     return 0;
  55. }
  56.  
  57. void generate(struct node **head, int num)
  58. {
  59.     struct node *temp = *head, *prev = *head;
  60.  
  61.     if (*head == NULL)
  62.     {
  63.         *head = (struct node *)malloc(sizeof(struct node));
  64.         (*head)->a = num;
  65.         (*head)->left = (*head)->right = NULL;
  66.     }
  67.     else
  68.     {
  69.         while (temp != NULL)
  70.         {
  71.             if (num > temp->a)
  72.             {
  73.                 prev = temp;
  74.                 temp = temp->right;
  75.             }
  76.             else
  77.             {
  78.                 prev = temp;
  79.                 temp = temp->left;
  80.             }
  81.         }
  82.         temp = (struct node *)malloc(sizeof(struct node));
  83.         temp->a = num;
  84.         if (num >= prev->a)
  85.         {
  86.             prev->right = temp;
  87.         }
  88.         else
  89.         {
  90.             prev->left = temp;
  91.         }
  92.     }
  93. }
  94.  
  95. int search(struct node *head, int key)
  96. {
  97.     while (head != NULL)
  98.     {
  99.         if (key > head->a)
  100.         {
  101.             head = head->right;
  102.         }
  103.         else if (key < head->a)
  104.         {
  105.             head = head->left;
  106.         }
  107.         else
  108.         {
  109.             return 1;
  110.         }
  111.     }
  112. 	return 0;
  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 pgm37.c
$ a.out
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 1
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 2
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 3
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 
4
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 2
Enter key to search: 1
Key found in tree
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 2
Enter key to search: 6
Key not found
 
Enter your choice:
1. Insert
2. Search
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.

If you find any mistake above, kindly email to [email protected]

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.