Trees/Preorder

Preorder traversal in trees

Preorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to Trees. The children do not necessarily need to be ordered - the order refers to the order of depth (bottom-up or top-down) and not order of children. In Binary Trees an Inorder Traversal can be defined that relies on the convention that in a sorted binary tree the left side comes before the right side.

Recursive definition

As with any recursive method, this must be split into a base case and a recursive case. The base case is, we've reached an external node - no children. The recursive case is, we call preorder on each child. In this case we don't need an explicit base case and recursive case.

The preorder traversal is the heuristic utilized in a "greedy" Traveling Salesperson Problem algorithm. See also: https://charlesreid1.github.io/ (several blog posts documenting implementations and profiling TSP code in Java).

Here is an example of a preorder traversal pseudocode:

define public function preorder( tree )
    preorder_subtree( tree, root, 0 )

define private function preorder_subtree( tree, position, depth)
    perform visit action on position
    for child in position.children():
        preorder_subtree(tree, child, depth+1)

Because this is an intransitive recursive function - nothing is returned - the base case can remain implicit (if position is an external node, position.children is empty, and the for loop is not run, and an instance of the void recursive method returns).