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.
I think it’s this tree:
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.
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==peekNode.right, then we just did the second recursive call. Otherwise we just did the first.