Iterative postorder binary tree traversal - why is this line of code needed?-CodePudding

I would very much appreciate your help with the following question.

I am trying to understand the pseudocode for iterative postorder binary tree traversal from the Wikipedia page Tree traversal.

I am not sure why is this part "and lastNodeVisited ≠ peekNode.right" in the second if-statement needed, i.e. I do not know when this part would evaluate to False.

Could anyone please provide an example of a binary tree in which "peekNode.right ≠ null" would evaluate to True, but "lastNodeVisited ≠ peekNode.right" would evaluate to False?

I tried creating a few binary trees of different shapes, but I could not find one in which, for a specific node, "peekNode.right ≠ null" would evaluate to True, but "lastNodeVisited ≠ peekNode.right" would evaluate to False.

CodePudding user response：

I think it's this tree:

      A
       \
        B

Iterations (on input A):

stack: [], lastNodeVisited: null, node: A. (Initial state before the first loop)
stack: [A], lastNodeVisited: null, node: null (A.left).
stack: [A], lastNodeVisited: null, node: B (A.right).
stack: [A, B], lastNodeVisited: null, node: null (B.left).
stack: [A], lastNodeVisited: B, node: null. visit(B) called.
stack: [], lastNodeVisited: A, node: null. visit(A) called.

Iteration #5, lastNodeVisited is B, peekNode is A, so peekNode.right = lastNodeVisited, but peekNode.right ≠ null.

If the check for lastNodeVisited ≠ peekNode.right weren't there, it would loop forever, between A and B, and it would never visit A.

CodePudding user response：

The iterative version of this traversal looks like this:

procedure recursivePostOrder(node)
    if node == null
        return
    recursivePostOrder(node.left)
    recursivePostOrder(node.right)
    visit(node)

When you translate this into an iterative implementation, you need to use your own stack instead of the call stack to do the recursion.

To replace each recursive call, you push some information that tells you what you were doing, and then change node and loop.

But notice that there are two recursive calls. Pushing node alone doesn't give you enough information to indicate where you left off -- maybe we should continue after the first call, or maybe after the second.

In your code, the extra information is provided by keeping track of lastNodeVisited. If lastNodeVisited==peekNode.right, then we just did the second recursive call. Otherwise we just did the first.