Language Implementation Patterns

Walking Trees and Visitation Order

When we talk about visiting a tree, we mean executing some actions on the nodes of a tree. The order in which we traverse the nodes is important because that affects the order in which we execute the actions. There are three key traversals:

• Preorder traversal or top-down traversal: + 1 2. Visit a (parent) node before visiting its children.

• Inorder traversal: 1 + 2. Visit a node in between visiting children.

• Postorder traversal or bottom-up traversal: 1 2 +. Visit a node after visiting its children.

Humans can pick out tree traversals by looking at a tree and, perhaps, tapping a pen on the nodes in a particular sequence. To implement this in code, we typically use a tree-walking algorithm called depth-first search ...