nonrecursive inorder traversal of a (ordinary) tree

Question

Usually in-order is defined for binary trees. Let's say that in-order is "extended" for (ordinary) trees. If tree is single node then that node is the in order traversal of the tree. If tree T is tree with T1, T2, ..., Tk sub trees and r as a root, then in-order of the T1 followed by the r followed by the in-order traversal of the T2, T3, ..,Tk is the in-order traversal of the T.
The T is given in left-child right-sibling representation. Data structure for the node in C is:

struct node {
   int data;
   struct node *left-child;
   struct node *right-sibling;
}

Tree is represented with a pointer to the root. Root cannot have right-sibling.
The question is to find an algorithm to traverse the tree in in-order. Recursion is not allowed. (Recursive algorithm is trivial).
I was trying to adapt the algorithm for the binary trees, for ordinary trees.
Let's consider the following tree:

          1
      /   |   \
     2    3    4

The inorder of this tree is 2 1 3 4.
If we consider the corresponding binary tree:

           1
        /
       2
         \
           3
             \
               4

we can see that in-order of this binary tree is 2 3 4 1. We can see that there is no correspondence between in-order of the ordinary trees and binary trees.
I don't have any idea how traverse ordinary tree in in-order.
What I have done so far:
Walk around the tree is the order of the nodes in which we start at the root, moving counterclockwise, and staying as close to the tree as possible. We print the nodes as we encounter them.
For in-order we list a leaf the first time we pass it, but list an interior node the second time we pass it.
Here is the code for a walk around a tree. This was quick hack so I am open for suggestions and improvements.

#include <stdio.h>
#include <stdlib.h>

typedef struct tree_node {
  int data;
  struct tree_node *left_child;
  struct tree_node *right_sibling;
} tree_node;


typedef struct stack_node {
  tree_node *data;
  struct stack_node *next;
} stack_node;


void pop( stack_node **p_s )
{
  if( *p_s == NULL ) {
    printf("Error: The stack is empty\n");
  }
  else {
    stack_node *tmp = *p_s;
    *p_s = (*p_s)->next;
    free( tmp );
  }
}

tree_node *top( stack_node *s )
{
  return s->data;
}

void push( tree_node *p_n, stack_node **p_s )
{
  stack_node *tmp = malloc( sizeof( stack_node ) );
  tmp->data = p_n;
  tmp->next = *p_s;
  *p_s = tmp;
}

tree_node *read_tree( void )
{
  printf("Does this tree is empty (y/n):");
  int c = getchar();
  int c1;
  while(( c1 = getchar() ) != '\n' && c1 != EOF );
  if( c == 'y' ) return NULL;
  else {
    tree_node *tmp = malloc( sizeof( tree_node ) );
    tree_node *root = tmp;
    root->right_sibling = NULL;
    stack_node *s = malloc( sizeof( stack_node ) );
    s->data = root;
    s->next = NULL; //Initialize the stack;
    int num_nod;
  state1:
    tmp = top( s );
    printf("Input the data for the node:");
    scanf("%d", &(tmp->data) );
    printf("How many children does this node have (0 for none):");
    scanf("%d", &num_nod);
    if( num_nod == 0 ) {
      tmp->left_child = NULL;
      goto state2;
    }
    else {
      tree_node *tmp2 = malloc( sizeof( tree_node ) );
      push( tmp2, &s );
      tmp->left_child = tmp2;
      for( int i = 1; i < num_nod; i++ ) {
    tmp2->right_sibling = malloc( sizeof( tree_node ) );
    tmp2 = tmp2->right_sibling;
      }
      tmp2->right_sibling = NULL;
      goto state1;
    }
    state2: if( root == top( s ) ) return root;
      tree_node *tmp2 = top( s );
      tmp2 = tmp2->right_sibling;
      pop( &s );
      if( tmp2 == NULL )
    goto state2;
      else {
    push( tmp2, &s );
    goto state1;
      }
  }
}

void walk( tree_node *t )
{
  if( t == NULL ) return;
  stack_node *s = malloc( sizeof( stack_node ) );
  s->data = t;
  s->next = NULL; //Initialize the stack;
  tree_node *tmp;
  tree_node *tmp2;
  tree_node *tmp3;
  printf("%d ", t->data );//We have visited the root, so print it.
  state1:
  tmp = top( s );
  tmp2 = tmp->left_child;
  if( tmp2 == NULL ) {
    goto state2;
  }
  else {
    push( tmp2, &s );
    printf("%d ", tmp2->data );
    goto state1;
  }
  state2:
  tmp = top( s );
  tmp2 = tmp->right_sibling;
  if( tmp == t ) {
    return;
  }
  pop( &s );
  tmp3 = top( s );
  printf("%d ", tmp3->data );
  if( tmp2 == NULL ) goto state2;
  else {
    push( tmp2, &s );
    printf("%d ", tmp2->data );
    goto state1;
 }
} 

int main()
{
  tree_node *t = read_tree();
  walk( t );
}

We can implement the algorithm for in-order in the following manner. Instead of listing the nodes in the walk() function we can store pointers to them in a list. Then we can analyze the list for interior nodes and list them only the second time they appear on the list. But, I don't like this algorithm. It uses too much memory, and it is slow. Any ideas are welcomed.

Answer 1

I think I have found the answer:

#include <stdio.h>
#include <stdlib.h>

typedef struct tree_node {
  int data;
  struct tree_node *left_child;
  struct tree_node *right_sibling;
} tree_node;


typedef struct stack_node {
  tree_node *data;
  struct stack_node *next;
} stack_node;


void pop( stack_node **p_s )
{
  if( *p_s == NULL ) {
    printf("Error: The stack is empty\n");
  }
  else {
    stack_node *tmp = *p_s;
    *p_s = (*p_s)->next;
    free( tmp );
  }
}

tree_node *top( stack_node *s )
{
  return s->data;
}

void push( tree_node *p_n, stack_node **p_s )
{
  stack_node *tmp = malloc( sizeof( stack_node ) );
  tmp->data = p_n;
  tmp->next = *p_s;
  *p_s = tmp;
}

tree_node *read_tree( void )
{
  printf("Does this tree is empty (y/n):");
  int c = getchar();
  int c1;
  while(( c1 = getchar() ) != '\n' && c1 != EOF );
  if( c == 'y' ) return NULL;
  else {
    tree_node *tmp = malloc( sizeof( tree_node ) );
    tree_node *root = tmp;
    root->right_sibling = NULL;
    stack_node *s = malloc( sizeof( stack_node ) );
    s->data = root;
    s->next = NULL; //Initialize the stack;
    int num_nod;
  state1:
    tmp = top( s );
    printf("Input the data for the node:");
    scanf("%d", &(tmp->data) );
    printf("How many children does this node have (0 for none):");
    scanf("%d", &num_nod);
    if( num_nod == 0 ) {
      tmp->left_child = NULL;
      goto state2;
    }
    else {
      tree_node *tmp2 = malloc( sizeof( tree_node ) );
      push( tmp2, &s );
      tmp->left_child = tmp2;
      for( int i = 1; i < num_nod; i++ ) {
    tmp2->right_sibling = malloc( sizeof( tree_node ) );
    tmp2 = tmp2->right_sibling;
      }
      tmp2->right_sibling = NULL;
      goto state1;
    }
    state2: if( root == top( s ) ) return root;
      tree_node *tmp2 = top( s );
      tmp2 = tmp2->right_sibling;
      pop( &s );
      if( tmp2 == NULL )
    goto state2;
      else {
    push( tmp2, &s );
    goto state1;
      }
  }
}

void nr_inorder( tree_node *t )
{
  if( t == NULL ) return;
  stack_node *s = malloc( sizeof( stack_node ) );
  s->data = t;
  s->next = NULL; //Initialize the stack;
  tree_node *tmp;
  tree_node *tmp2;
  tree_node *tmp3;
  state1:
  tmp = top( s );
  tmp2 = tmp->left_child;
  if( tmp2 == NULL ) { //tmp is a leaf so print it
    printf("%d ", tmp->data );
    goto state2;
  }
  else {
    push( tmp2, &s );
    goto state1;
  }
  state2:
  tmp = top( s );
  tmp2 = tmp->right_sibling;
  if( tmp == t ) {
    return;
  }
  pop( &s );
  tmp3 = top( s );
  if( (tmp3->left_child)->right_sibling == tmp2 ) /* This is the whole trick.
  Basically it states if we are visiting tmp3 for the second time then ... */
    printf("%d ", tmp3->data );
  if( tmp2 == NULL ) goto state2;
  else {
    push( tmp2, &s );
    goto state1;
 }
} 

int main()
{
  tree_node *t = read_tree();
  nr_inorder( t );
}  

This is the quick hack, and I don't know if it is correct answer. Any suggestions and improvements are welcomed. I have tried on few trees and the in-order was correct.

Answer 2

The standard mechanism of in-order traversal of a tree without recursion is by using an extra stack collection/data structure.

The interwebz abount with solutions to this problem, for example here is a youtube video: https://www.youtube.com/watch?v=kqdtyJPeJ8g