Problem with Stack based Euler-Tree-traversal

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