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;
}

Can you show the `BinaryTree` interface? Is it possible to get the parent of a tree node? — Arnout Engelen, Sep 25 '11 at 19:36
possible duplicate of [Can every recursion be converted into iteration?](http://stackoverflow.com/q/931762/), [Design patterns for converting recursive algorithms to iterative ones](http://stackoverflow.com/q/1549943/) — outis, Jun 20 '12 at 22:40

score 4 · Accepted Answer · answered Sep 25 '11 at 19:42

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?

answered Sep 25 '11 at 19:42

user541686

205,094
128
528
886

1

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. – Kraken Sep 25 '11 at 19:44
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? – Kraken Sep 25 '11 at 19:58
kindly help me out a bit more with the stack thing, if you can. – Kraken Sep 25 '11 at 20:10
@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. – user541686 Sep 25 '11 at 20:14
@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? – user541686 Sep 25 '11 at 20:21
it does not give the right sequence, i dont think i am able to go up the tree. – Kraken Sep 25 '11 at 20:23
yeah, that is for checking the emptiness. But, i m not getting the desired result. Inorder traversal is not achieved. – Kraken Sep 25 '11 at 20:25
and why should it, because after i reach the left most leaf of any subtree, i am just popping once, that takes me one step higher in the tree, i dont think, i will be ever able to traverse up by more that one node. Or am i wrong? – Kraken Sep 25 '11 at 20:26
@Karan: I just tested your program in another language and it ran fine. Are you sure your tree is correct? What output do you get? – user541686 Sep 25 '11 at 20:32
sorry it was correct, i thought it to out =put the wrong order. Thanks. – Kraken Sep 25 '11 at 20:33
and yeah , i get it how i would be able to go up the tree, since when i pop the node, it no longer stays in the stack(obviously) and the next time pop the node, it takes me one step ahead. So i guess, the way to go from recursive to iterative is that, you see how your stack is going to behave and accordingly implement it, right? – Kraken Sep 25 '11 at 20:37

Dagang · Answer 2 · 2017-11-14T04:46:09.363

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.

edited Nov 14 '17 at 04:46

answered Nov 13 '17 at 19:46

Dagang

24,586
26
88
133

Arnout Engelen · Answer 3 · 2011-09-25T20:05:21.130

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

edited Sep 25 '11 at 20:05

answered Sep 25 '11 at 19:55

Arnout Engelen

6,709
1
25
36

i was also going for something like this only, But this does count as an iterative version right? – Kraken Sep 25 '11 at 20:01
also, i dont think this is an inorder traversal, as for the matter of fact, you started printing from the root. – Kraken Sep 25 '11 at 20:04
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. – Arnout Engelen Sep 25 '11 at 20:04

score 0 · Answer 4 · answered Sep 25 '11 at 20:38

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.

Convert recursive binary tree traversal to iterative

4 Answers4

Linked