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.

```
/*
```

 * C Program to Implement Depth First Search Traversal using Post Order

```
       50
```
```
      /  \
```
```
    20   30
```
```
   /  \    
```
```
  70  80
```
```
 /  \    \
```
```
10  40   60    
```
```
(50, 20, 30, 70, 80, 10, 40, 60)
```
```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct btnode {
```
```
    int value;
```
```
    struct btnode *l;
```
```
    struct btnode *r;
```
```
};
```
```
 
```
```
typedef struct btnode bt;
```
```
bt *root;
```
```
bt *new, *list;
```
```
bt *create_node();
```
```
void display(bt *);
```
```
void construct_tree();
```
```
void dfs(bt *);
```
```
 
```
```
void main()
```
```
{
```
```
    construct_tree();
```
```
    display(root);
```
```
    printf("\n");
```
```
    printf("Depth first traversal\n ");
```
```
    dfs(root);
```
```
}
```
```
 
```
```
/* Creates an empty node */
```
```
bt * create_node()
```
```
{
```
```
    new=(bt *)malloc(sizeof(bt));
```
```
    new->l = NULL;
```
```
    new->r = NULL;
```
```
}
```
```
 
```
```
/* Constructs a tree */
```
```
void construct_tree()
```
```
{
```
```
    root = create_node();
```
```
    root->value = 50;
```
```
    root->l = create_node();
```
```
    root->l->value = 20;
```
```
    root->r = create_node();
```
```
    root->r->value = 30;
```
```
    root->l->l = create_node();
```
```
    root->l->l->value = 70;
```
```
    root->l->r = create_node();
```
```
    root->l->r->value = 80;
```
```
    root->l->r->r = create_node();
```
```
    root->l->r->r->value = 60;
```
```
    root->l->l->l = create_node();
```
```
    root->l->l->l->value = 10;
```
```
    root->l->l->r = create_node();
```
```
    root->l->l->r->value = 40;      
```
```
}
```
```
 
```

/* Display the elements in a tree using inorder */

```
void display(bt * list)
```
```
{
```
```
    if (list == NULL)
```
```
    {
```
```
        return;
```
```
    }
```
```
    display(list->l);
```
```
    printf("->%d", list->value);
```
```
    display(list->r);
```
```
}
```
```
 
```
```
/* Dfs traversal using post order */
```
```
void dfs(bt * list)
```
```
{
```
```
    if (list == NULL)
```
```
    {
```
```
        return;
```
```
    }
```
```
    dfs(list->l);
```
```
    dfs(list->r);
```
```
    printf("->%d ", list->value);
```
```
}
```

        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.

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.

« Prev - C Program to Find Majority Element in a Sorted Array

» Next - C Program to Implement Insertion Sort

Related Posts:

Recommended Articles: