Wsrtjtyk

I want a function that traverses a binary tree with the Euler traversal (this is how it works). Of course this is easily achievable with recursion - I know how that works. But now I want to implement an iterative version of this algorithm using a stack instead of recursion. My idea was to store the direction we are traversing on the stack as well. My code is not working and I can somehow not wrap my mind around this problem. Can you give me any hints on how to tackle this issue? Here is my code so far:

#define LEFT (struct Node*) 0xBADF00D

#define RIGHT (struct Node*) 0xDEADBEEF



struct Node { 

    int data; 

    struct Node* parent; 

    struct Node* left; 

    struct Node* right; 

}; 



void eulerTree(struct Node* root) 

{ 

    stack<struct Node*> s;



    s.push(root);

    s.push(RIGHT);

    s.push(root);

    s.push(LEFT);



    while(!s.empty()) {

        struct Node* direction = s.top(); s.pop();

        struct Node* node = s.top(); s.pop();



        visit(node);



        if(direction == LEFT) {

            if(node->left) {

                s.push(node->left);

                s.push(RIGHT);



                s.push(node->left);

                s.push(LEFT);

            }

        } 



        if(direction == RIGHT) {

            if(node->right) {

                s.push(node->right);

                s.push(RIGHT);



                s.push(node->right);

                s.push(LEFT);

            }

        }

    }

}

Think of a simple binary tree to start with :

           1

        2     3

Euler traversal for this is : 1 2 1 3 1

You see the pattern here:
root, root->left, root, root->right, root

So your stack order should be:

root

root->left

root

root->right

root

But what if your root is a leaf? then don't push anything just print the value.

Also once you push the nodes on left, right make sure you set them as 0 for the root so that you don't keep pushing them forever.

With that said, the code in cpp would be:

Edit:

The previous code I posted has a bug. The correct code is below:

void eulerTree(struct Node* root) 

{ 

    stack<struct Node*> s;



    s.push(root);





    while(!s.empty()) {



        struct Node* node = s.pop();



        visit(node);



        if(node->right) {

          s.push(node);

          s.push(node->right);

        }



        if(node->left) {

          s.push(node);

          s.push(node->left);

        }

        node->left = 0;

        node->right = 0;

    }

}

Without destroying the tree:

But yes, even though the code is simple this destroys the tree which is not desired. To tackle this problem I am going to use two properties for leaves of the tree in a euler tree traversal.

1. 
   

   If the leaf is left child of the parent and the right child of that parent is null

   
   
   

   ( or )

   
   
   

   if the leaf is right child

   
   
   

   -after this leaf is printed then print the parent nodes all the way up the root.

   
   


2. 
   

   If the leaf is left child and the right child is not null

   
   
   

   -after this leaf is printed then print only its immediate parent.

   
   

To illustrate look at the below tree.


1
2 3
4 5 6 7


If the leaf is 5 then after it is printed, then print all the parents upto 1.

If the leaf is 4 then after it is printed, then print just its immediate parent 2.

To simplify implementation I am going to use a parent stack in addition to the current stack.

void eulerTree(struct Node* root) {

  stack<struct Node*> s;

  s.push(root);

  struct Node* original = root;

  stack<struct Node*> p;



  while(!s.empty()) {

    struct Node* node = s.top();

    s.pop();



    visit(node);



    if ( !node->right && !node->left && !p.empty() ) {

      struct Node* pNode = p.top();

      if ( pNode->left == node && !pNode->right  || pNode->right == node ) {

        while ( !p.empty() ) {

          visit(p.top());

          p.pop();

        }

        p.push(original);

      } else {

        visit(pNode);

      }

    }



    if(node->left || node->right) {

      p.push(node);

    }



    if(node->right) {

      s.push(node->right);

    }



    if(node->left) {

      s.push(node->left);

    }

  }

}

A recursive implementation might look like this:

void euler(Node *n) {

    visit(n);

    if (n->left) {

        euler(n->left);

        visit(n);

    }

    if (n->right) {

        euler(n->right);

        visit(n);

    }

}

Now whenever this makes a recursive call, the call stack is used to remember where we are in the code and what we're doing. Then we start again at the top and when we're done, that information is popped of the stack and we continue where we left off.

If you're going to do it iteratively with your own stack, you have to do the same job yourself. You have to remember enough to continue where you left off.

We have to remember which node we were working on of course, but also there are two recursive calls so, so there are 2 possible places we might have to return to. When we return from a recursive call, then either:

1. We have just done the n->left call and should continue on to check n->right; OR


2. We have just done the n->right call and should continue with the final visit of n
   

We could store some extra information on the stack to distinguish these two cases, but that is not necessary for this particular algorithm. From the descriptions above, you can see that we can distinguish these cases based on the node we're returning from -- it's either n->left or n->right.

So, just storing the waiting node in the stack, we can write an iterative version like this:

int state=0; // 0 => initial visit, 1 => just did left, 2 => just did right

Node *n = root;

while (n) {

    visit(n);



    if (n->left && state<1) {

        stack.push(n);

        n=n->left;

        state=0;

        continue;

    }



    if (n->right && state<2) {

        stack.push(n);

        n=n->right;

        state=0;

        continue;

    }



    if (stack.empty())

        break; // done



    Node *child=n;

    n = stack.pop();

    state = (child == n->left ? 1 : 2);

}