post order traversal in binary tree using one stack

Question

I want to make a post order traversal of a binary tree using one stack only. This is my code , first of all i am pushing left elements into the stack till I reach null. Then I pop an element and check whether the popped out element and the right element of the current stack top is same or not. But somehow this is going into infinite loop. can you tell me why??

public void postorderonestack(BinNode root)
{
    BinStack s=new BinStack();

    while(true)
    {
        if(root!=null)
        {
           s.push(root);
           root=root.getLeft();
        }
        else
        {
            if(s.isEmpty())
            {
                System.out.println("Stack is Empty");
                return;
            }

            else if( s.top().getRight()==null)
            {
                root=s.pop();
                System.out.println(root.getKey());

                if(root==s.top().getRight())
                {
                   System.out.print(s.top().getKey());
                   s.pop();
                }
            }

            if(!s.isEmpty())
              root=s.top().getRight();

           else root=null;
        }
    }
}

Answer 1

This is the code from my answer to another question (Post order traversal of binary tree without recursion). It works with one stack and doesn't use visited flag.

private void postorder(Node head) {
  if (head == null) {
    return;
  }
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(head);

  while (!stack.isEmpty()) {
    Node next = stack.peek();

    if (next.right == head || next.left == head ||
        (next.left == null && next.right == null)) {
      stack.pop();
      System.out.println(next.value);
      head = next;
    }
    else {
      if (next.right != null) {
        stack.push(next.right);
      }
      if (next.left != null) {
        stack.push(next.left);
      }
    }
  }
}

Answer 2

Why not do it recursively?

public void postorder(BinNode root) {
    if (root == null)
        return;
    postorder(root.getLeft());
    postorder(root.getRight());
    System.out.println(root.getKey());
}

Answer 3

There is an infinite loop in this code lets consider an Right skewed tree to illustarte this:

1 has a right child 2

2 has a right child 3

3 is a leaf node

In first 3 loops 1 follwed by 2 followed by 3 will be pushed on to the stack. Now on fourth loop it enters else part now it prints 3 followed by 2 and pops both.

after the statement

else if( s.top().getRight()==null) 

the statement

if(!s.isEmpty()) 

will push 2 again on stack. This causes infinite loop.

The code is flawed.

The statement

if(root==s.top().getRight()) 

should become a while loop to fix this issue.