1#include <stdlib.h>
2#include <stdio.h>
3#include "bin-trees.h"
4
5static void
6real_in_order_traverse_no_recurse (tree_ptr root)
7{
8  struct stack_struct *stack = NULL;
9  tree_ptr current= root;
10  int going_left = 1;   /* boolean variable */
11  while (current != NULL)
12  {
13    if ((current->left != NULL) && going_left)
14    {
15      push (&stack, current);
16      current = current->left;
17    }
18
19    printf ("%d ", current->data);
20    if (current->right)
21    {
22      current = current->right;
23      going_left = 1;
24    }
25    else if (stack != NULL)
26    {
27      current = pop(&stack);
28      going_left = 0;
29    }
30    else
31      current = NULL;
32  }
33}
34
35void
36in_order_traverse_no_recurse (tree_ptr root)
37{
38  printf ("in-order traversal, without recursion: \n");
39  real_in_order_traverse_no_recurse (root);
40  printf ("\n");
41  return;
42}
43