Trees/Postorder

Postorder traversal in trees

Postorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to Trees, very similar to Trees/Preorder (preorder traversal). Postorder is a bottom-up traversal, where the visit action is performed as the recursive functions return off the stack.

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 postorder traversal is the patient, wait-and-see heuristic.

Here is an example of a postorder traversal pseudocode:

define public function postorder( tree )
    postorder_subtree( tree, root, 0 )

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

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).