C Program to Implement Depth First Search Traversal using Post Order

This C Program implements depth first search traversal using post order.

Here is source code of the C Program to implement depth first search traversal using post order. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Implement Depth First Search Traversal using Post Order
  3.        50
  4.       /  \
  5.     20   30
  6.    /  \    
  7.   70  80
  8.  /  \    \
  9. 10  40   60    
  10. (50, 20, 30, 70, 80, 10, 40, 60)
  11.  */
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. struct btnode {
  16.     int value;
  17.     struct btnode *l;
  18.     struct btnode *r;
  19. };
  20.  
  21. typedef struct btnode bt;
  22. bt *root;
  23. bt *new, *list;
  24. bt *create_node();
  25. void display(bt *);
  26. void construct_tree();
  27. void dfs(bt *);
  28.  
  29. void main()
  30. {
  31.     construct_tree();
  32.     display(root);
  33.     printf("\n");
  34.     printf("Depth first traversal\n ");
  35.     dfs(root);
  36. }
  37.  
  38. /* Creates an empty node */
  39. bt * create_node()
  40. {
  41.     new=(bt *)malloc(sizeof(bt));
  42.     new->l = NULL;
  43.     new->r = NULL;
  44. }
  45.  
  46. /* Constructs a tree */
  47. void construct_tree()
  48. {
  49.     root = create_node();
  50.     root->value = 50;
  51.     root->l = create_node();
  52.     root->l->value = 20;
  53.     root->r = create_node();
  54.     root->r->value = 30;
  55.     root->l->l = create_node();
  56.     root->l->l->value = 70;
  57.     root->l->r = create_node();
  58.     root->l->r->value = 80;
  59.     root->l->r->r = create_node();
  60.     root->l->r->r->value = 60;
  61.     root->l->l->l = create_node();
  62.     root->l->l->l->value = 10;
  63.     root->l->l->r = create_node();
  64.     root->l->l->r->value = 40;      
  65. }
  66.  
  67. /* Display the elements in a tree using inorder */
  68. void display(bt * list)
  69. {
  70.     if (list == NULL)
  71.     {
  72.         return;
  73.     }
  74.     display(list->l);
  75.     printf("->%d", list->value);
  76.     display(list->r);
  77. }
  78.  
  79. /* Dfs traversal using post order */
  80. void dfs(bt * list)
  81. {
  82.     if (list == NULL)
  83.     {
  84.         return;
  85.     }
  86.     dfs(list->l);
  87.     dfs(list->r);
  88.     printf("->%d ", list->value);
  89. }

        50
       /  \
     20    30
     / \    
   70    80
  /  \     \
 10  40    60
$ cc tree29.c
$ a.out
->10->70->40->20->80->60->50->30
Depth first traversal
->10->40->70->60->80->20->30->50

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 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.