Convert recursive binary tree traversal to iterative

Question

I was asked to write the iterative version, but I wrote the recursive version i.e.

void inorderTraverse(BinaryTree root)
{
    if(root==NULL)
        printf("%d",root->id);
    else
    {
        inorderTraverse(root->left);
        printf("%d",root->id);
        inorderTraverse(root->right);
    }
}

I'm not looking for the code, I want to understand how this can be done. Had it been just the last recursive call, I would have done

void inorderTraverse(BinaryTree root)
{
    while(root!=NULL)
    {
        printf("%d",root->id);
        root=root->right;
    }
}

But how do I convert to an iterative program when there are two recursive calls?

Here are the type definitions.

struct element{
    struct element* parent;
    int id;
    char* name;
    struct element* left;
    struct element* right;
};
typedef element* BinaryTree;

This is what I thought of, am I on the right track?

temp=root;
while(1)
{
    while(temp!=NULL)
    {
     push(s,temp);
     temp=temp->left;
     continue;
    }

    temp=pop(s);
    if(temp==NULL)
    return;
    printf("%d\t",temp->data);
    temp=temp->right;
}

Answer 1

The problem you're seeing is that you need to "remember" the last place you were iterating at.
When doing recursion, the program internally uses "the stack" to remember where to go back to.
But when doing iteration, it doesn't.

Although... does that give you an idea?

Answer 2

I can't think of a really elegant way to do this iteratively off-hand.

One possibility might be using a 'mark algorithm', where you start out with all nodes 'unmarked' and 'mark' nodes as they're handled. The markers can be added to the object model or kept in a seperate entity.

Pseudocode:

for (BinaryTree currentNode = leftmostNode(root); currentNode != null; currentNode = nextNode(currentNode)):
  print currentNode;
  currentNode.seen = true;

sub nextNode(BinaryTree node):
  if (!node.left.seen):
    return leftmostNode(node.left)
  else if (!node.seen)
    return node
  else if (!node.right.seen)
    return leftmostNode(node.right)
  else 
    return nextUnseenParent(node)

sub leftmostNode(BinaryTree node):
  while (node.left != null)
    node = node.left
  return node;

sub nextUnseenParent(BinaryTree node):
  while (node.parent.seen)
    node = node.parent
  return node.parent

Answer 3

I take it for granted, that iterating down from the parent nodes to the left nodes is not a problem. The problem is to know what to do when going up from one node to the parent: should you take the right child node or should you go up one more parent?

The following trick will help you:

Before going upwards remember the current node. Then go upwards. Now you can compare: Have you been in the left node: Then take the right node. Otherwise go up one more parent node.

You need only one reference/pointer for this.

Answer 4

There is a general way of converting recursive traversal to iterator by using a lazy iterator which concatenates multiple iterator suppliers (lambda expression which returns an iterator). See my Converting Recursive Traversal to Iterator.