5.10 Traversal

We often want to “visit” all the nodes of a tree in a sequence, or traverse the tree. In the semantics phase, it is often necessary to visit all the children of a node before the node itself. We can do this using a postorder traversal traversal. Here is a recursive procedure for a postorder traversal of the tree nd:

         If nd is not well-defined, return
         Traverse the children of nd, in order
         Visit nd

A postorder traversal is also often called a depth-first traversal, or a bottom-up traversal. A postorder traversal of our example tree (see An example tree) visits the nodes in the following order:

    T U A B V C W X D Y Z E S