Postorder Traversal Algorithm

 

Postorder Traversal Algorithm in Data Structures:

Postorder Traversal Algorithm

The Postorder traversal algorithm is more complicated than other algorithms, because in Postorder traversal algorithm 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. (In actual practice, the location N is pushed onto STACK, so -N has the obvious meaning). 
 
Again, a variable PTR (pointer) is used which contain the location of the node N that is currently being scanned.


The algorithm of Postorder Traversal

Initially push NULL onto STACK(as a sentinel) and then set PTR=ROOT. Then repeat the following steps until NULL is popped from STACK.
(a) proceed down the left-most path rooted at PTR. At each node N of the path, push N onto STACK and, if N has right child R(N), push -R(N) onto STACK.
(b)[Backtracking.] Pop and process positive nodes on STACK. If NULL is popped, then Exit. If a negative node is popped, that is, if PTR=-N for some node N, set PTR=N (by assigning PTR=-PTR) and return on Step (a).
We emphasize that a node N is processed only when it is popped from STACK and it is positive.
 

PostOrder Traversal Algorithm:

POSTORD(INFO,LEFT,RIGHT,ROOT)
A binary tree T is in memory. This algorithm does the 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.
 
1 [Push NULL onto STACK and initialize PTR.]
set TOP=1,STACK[1]=NULL and PTR=ROOT.
2 [Push left-most path onto STACK.]
Repeat Steps 3 to 5 while PTR!NULL.
[pushes PTR on STACK.]
4 If RIGHT[PTR]!NULL, then:[Push on STACK]
Set TOP=TOP+1 and STACK[TOP]=-RIGHT[PTR]
[End of if structure].
5 Set PTR=LEFT[PTR].[Update pointer PTR.]
[End of step 2 loop.]
6 Set PTR=STACK[TOP] and TOP=TOP-1.
[Pops node from STACK]
7 Repeat while PTR>0
(a) Apply PROCESS to  INFO[PTR].
(b) Set PTR=STACK[TOP] and TOP=TOP-1
[Pops node from STACK.]
[End of loop]
8 If PTR<0, then:
(a) Set PTR=-PTR
(b) Go to Step 2.
[End of if structure]
9 Exit.