is wikipedia iterative postorder tree traversal pseudo code wrong?

Question

Here is the pseudo code that wikipedia gives for iterative postorder tree traversal.

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node from left child, move right */
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

It is pretty straight forward, and I have implemented it in Java. But it does not work, the problem is that every time it visits the most left leaf and return to its parent, it will add that left leaf again into the stack in next iteration. This causes an infinite loop. Is my method incorrect or the wikipedia version is wrong?

public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if (root == null) return res;
    Stack<TreeNode> s = new Stack<TreeNode>();
    TreeNode lastVisitedNode = null;
    TreeNode curr = root;
    int i = 0;
    while (curr != null || !s.isEmpty()) {
        if (curr != null) {
            System.out.println("push " + curr.val);
            s.push(curr);
            curr = curr.left;
        } else {
            curr = s.peek();
            if (curr.right != null && lastVisitedNode != curr.right) {
                curr = curr.right;
            } else {
                res.add(curr.val);
                System.out.println("pop " + curr.val);
                lastVisitedNode = s.pop();
            }
        }
        System.out.println(s);
        System.out.println(res);
        if (i>8) break;
        else i++;
    }
    return res;
}

Answer 1

The wikipedia version is wrong for the exact same reason as you've explained it.

Here is a probably better pseudo-code, from geeksforgeeks

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

You will have to add extra code to check if the node right child is null in 2.1.a though.

Answer 2

The wikipedia pseudocode is not wrong. They use two different variables: node and peekNode, while you only use curr for both. Node == null refers to the case when there is no more of a left branch left to explore, so we can stop pushing and instead investigate the next element in the stack. You can either revert to using two different variables, or you make the following fix in your code:

Since you reassign curr to a non-null value everytime you investigate the stack, you need to reset curr to null after you visit your node. (Because the state that still no more left branch left to explore is still unchanged).

The wikipedia pseudocode doesn't have to do this because their node value remains null.

Here is my code which gives a perfect answer:

var currentNode = this.root()
var previousNode = null
while(!nodeStack.isEmpty() || currentNode) {

    // If there is a node on which the recursive call is made, we have a subtree to explore. If this is null, we have to backtrack and do a callback. 
    if (currentNode) {
        nodeStack.push(currentNode)
        previousNode = currentNode
        currentNode = currentNode.leftChild
    } else {
        currentNode = nodeStack.peek()
        if (currentNode.rightChild && previousNode != currentNode.rightChild) {
            currentNode = currentNode.rightChild    
        } else {
            callback(currentNode)
            currentNode = null
            previousNode = nodeStack.pop()
        }
    } 
}