iterative inorder tree traversal

gistfile1.txt

#include <stdio.h>
#include <string.h>

struct node {
  char c;
  node * left;
  node * right;
};


/*
         1
       2   3
      4 5 6 7

         a
       b   c
      d e f g
*/

void inorder(node *n) {
  if ( n != NULL ) {
    inorder(n->left);
    printf("%c", n->c);
    inorder(n->right);
  }
}

void inorder_iter(node *n) {
  node * arr[16];
  int state[16];
  int i = 0;

  memset(state, 0, sizeof(int)*16);
  arr[i] = n;

  while ( i >= 0 ) {
    if ( arr[i] == NULL || state[i] == 2 ) {
      i--;
    } else {
      if ( state[i] == 0 ) {
        arr[i+1] = arr[i]->left;
      } else {
        printf("%c", arr[i]->c);
        arr[i+1] = arr[i]->right;
      }

      state[i]++;
      i++;
      state[i] = 0;
    }
  }
}

int main() {
  node arr[7];
  printf("Initializing...");
  for ( int i = 0; i < 7; i++ ) {
    arr[i].c = 'a'+i;
    int child = (i+1)*2;
    arr[i].left = child >= 7 ? NULL : &arr[child-1];
    arr[i].right = child >= 7 ? NULL : &arr[child];
  }
  printf("done.\n");

//  arr[2].left = NULL;
//  arr[2].right = NULL;

  for ( int i = 0; i < 7; i++ ) {
    printf("%p node[%d] = {%c, %p, %p}\n", &arr[i], i, arr[i].c, arr[i].left, arr[i].right);
  }

  printf("*****\n");

  inorder(&arr[0]);
  printf("\n");
  inorder_iter(&arr[0]);
  printf("\n");
  return 0;
}