Tree Postorder traversal Algorithm

The Postorder traversal algorithm is more complicated than the preceding two algorithms, because here we may have to save a node N in two different situations. We distinguish between the two cases by pushing either N or its negative –N, onto STACK. Again, a variable PTR (pointer) is used which contains the location of the node N that is currently being scanned.

Algorithm Post-order Traversal 

POSTORD(INFO, LEFT, RIGHT, ROOT)

A binary tree T is in memory. This algorithm does a postorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes.

Step I: [Initially push NULL onto STACK, and initialize PTR.]
Set TOP := 1, STACK[TOP] := NULL and PTR := ROOT.

Step II: Repeat steps 3 to 5 while PTR != NULL.

Step III: [Push left path onto STACK.]
Set TOP := TOP + 1 and STACK[TOP] := PTR.

Step IV: If RIGHT[PTR] != NULL, then: [Push on STACK.]
Set TOP := TOP + 1, and
STACK[TOP] := -RIGHT[PTR].
[End of If structure.]

Step V: Set PTR := LEFT[PTR]. [Updates pointer PTR.]
[End of step 2 loop.]

Step VI: Set PTR := STACK[TOP] and TOP := TOP – 1.
[Pops node from STACK.]

Step VII: Repeat while PTR > 0;
Apply PROCESS to INFO[PTR].
Set PTR := STACK[TOP] and TOP := TOP – 1.
[Pops node from STACK.]
[End of loop 7.]

Step VIII: If PTR < 0; then:
Set PTR := -PTR.
Go to step 2.
[End of If structure.]

Step IX: Exit.