javadata-structuresbinary-treetree-traversal

post order traversal in binary tree using one stack


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

Solution

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