Example code demonstrating tree traversal in DFS

test-treetrv.c

// demonstrate tree traversal
#include <stdio.h>
#include <stdlib.h>

typedef struct node node;
struct node
{
  struct node* child[2];
  char id;
};

static void free_all_nodes(node* n)
{
  if (n != NULL)
  {
    free_all_nodes(n->child[0]);
    free_all_nodes(n->child[1]);
    
    // delete the node
    // note: we will always be at the leaf node
    n->child[0] = NULL;
    n->child[1] = NULL;
    printf("free %c node\n", n->id);
    free(n);
    n = NULL;
  }
}

static void visit(node* n)
{
  printf("visit %c\n", n->id);
}

static void trv_preorder(node* n)
{
  if (n != NULL)
  {
    visit(n);
    trv_preorder(n->child[0]);
    trv_preorder(n->child[1]);
  }
}

static void trv_inorder(node* n)
{
  if (n != NULL)
  {
    trv_inorder(n->child[0]);
    visit(n);
    trv_inorder(n->child[1]);
  }
}

static void trv_postorder(node* n)
{
  if (n != NULL)
  {
    trv_postorder(n->child[0]);
    trv_postorder(n->child[1]);
    visit(n);
  }
}

int main (int argc, char** argv)
{
  // form the tree according to
  // image in wiki page
  // see https://en.wikipedia.org/wiki/Tree_traversal
  node* root = malloc(sizeof(node));
  root->id = 'F';

  node* node_a = malloc(sizeof(node));
  node_a->id = 'A';
  node_a->child[0] = NULL;
  node_a->child[1] = NULL;

  node* node_c = malloc(sizeof(node));
  node_c->id = 'C';
  node_c->child[0] = NULL;
  node_c->child[1] = NULL;

  node* node_e = malloc(sizeof(node));
  node_e->id = 'E';
  node_e->child[0] = NULL;
  node_e->child[1] = NULL;

  node* node_d = malloc(sizeof(node));
  node_d->id = 'D';
  node_d->child[0] = node_c;
  node_d->child[1] = node_e;

  node* node_b = malloc(sizeof(node));
  node_b->id = 'B';
  node_b->child[0] = node_a;
  node_b->child[1] = node_d;

  root->child[0] = node_b;

  node* node_h = malloc(sizeof(node));
  node_h->id = 'H';
  node_h->child[0] = NULL;
  node_h->child[1] = NULL;

  node* node_i = malloc(sizeof(node));
  node_i->id = 'I';
  node_i->child[0] = node_h;
  node_i->child[1] = NULL;

  node* node_g = malloc(sizeof(node));
  node_g->id = 'G';
  node_g->child[0] = NULL;
  node_g->child[1] = node_i;
  
  root->child[1] = node_g;

  // now time for traversal
  printf("--traverse preorder--\n\n");
  trv_preorder(root);

  printf("--traverse inorder--\n\n");
  trv_inorder(root);

  printf("--traverse postorder--\n\n");
  trv_postorder(root);

  printf("--free all nodes--\n\n");
  free_all_nodes(root);
  
  return 0;
}