4

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;
}
Improve this question
2

4 Answers 4

Reset to default
4

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?

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

i know it has got something to do with pushing the things on stack and then popping them, but i really cant figure this out, like what to push, when to pop, and how.
ok, i can start by pushing all the nodes, till i reach the leftmost leaf, now after that i start popping,now after popping first one, i push the right child on stach, and keep pushing till i reach the leftmost leaf of this subtree, now i go to the right tree, and reach the right most leaf of that subtree, but now how would i know how much pops do i need to do so that i reach the parent of the leftmost leaf of the original tree?
kindly help me out a bit more with the stack thing, if you can.
@Karan: I'm not sure if I quite followed what you mentioned, but what you want to do is to do this: (1) push the current node and keep pushing its left children as many times as you can (i.e. until there is no left node), (2) pop the last node (this has the return value), (3) repeat step 1 with the right child, if any, of the last node you popped.
@Karan: I'm not sure why you have if(temp==NULL) in your code -- you never push a NULL, so why should you pop a NULL? Or is that supposed to signal an emptiness condition? But aside from that, it seems fine... have you tried it?
|
0

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
Improve this answer

3 Comments

i was also going for something like this only, But this does count as an iterative version right?
also, i dont think this is an inorder traversal, as for the matter of fact, you started printing from the root.
The 'iteration step' is a bit more complicated than usual, but it contains only for loops, while loops and no recursive calls, so I'd say it should qualify as iterative.
0

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.