Preorder Traversal Algorithm

The preorder traversal algorithm uses a variable PTR (pointer) which will contain the location of the node N currently being scanned. Here L(N) denotes the left child of node N and R(N) denotes the right child. The algorithm also uses an array STACK, which will hold the addresses of nodes for future processing.

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

A binary tree T is in memory. This algorithm does a preorder 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: Apply PROCESS to INFO[PTR].
Step IV: [Right child?]
If RIGHT[PTR] != NULL, then: [Push on STACK.]
Set TOP := TOP + 1, and
STACK[TOP] := RIGHT[PTR].
[End of If structure.]
Step V: [Left child?]
If LEFT[PTR] != NULL, then:
Set PTR := LEFT[PTR]
Else: [Pop from STACK.]
Set PTR := STACK[PTR], and
TOP := TOP – 1.
[End of If structure.]
[End of step 2 loop.]
Step VI: Exit