Tree Inorder traversal algorithm

The inorder traversal algorithm also uses a variable pointer PTR, which will contain the location of the node N currently being scanned, and an array STACK, which will hold the addresses of nodes for future processing. In fact, with this algorithm, a node is processed only when it is popped from STACK.

Algorithm: INORD(INFO, LEFT, RIGHT, ROOT)

A binary tree T is in memory. This algorithm does an inorder 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: [Push left path onto STACK.]
Repeat while PTR != NULL.
(i) Set TOP := TOP + 1 and STACK[TOP] := PTR. [Saves node.]
(ii) Set PTR := LEFT[PTR]. [Update PTR.]
[End of loop.]

Step III: [Initialize pointers and pop first top element from STACK.]
Set PTR := STACK[TOP] and TOP := TOP – 1.
Step IV: Repeat steps 5 to 7 while PTR != NULL. [Backtracking.]

Step V: Apply PROCESS to INFO[PTR].

Step VI: [Right child?]
If RIGHT[PTR] != NULL, then:
(i) Set PTR := RIGHT[PTR]
(ii) Go to step 2.
[End of If structure.]

Step VII: Set PTR := STACK[TOP] and TOP := TOP – 1. [Pops node.]
[End of step 4 loop.]

Step VIII: Exit.