Traversing a tree depth-first

This recipe will demonstrate one way to traverse through a tree. The algorithm starts at the root node and continues exploring nodes along the entire length of a branch before going back to explore more shallow nodes.

Since we will examine each node before recursively examining its child nodes, we call this a pre-order traversal. Instead, if we examine each node afterwards, then we call this approach post-order traversal. Anything in-between is an in-order traversal, but naturally, there is no unique in-order traversal for rose trees.

The biggest advantage in using the depth-first approach is the minimal space complexity. Video game AIs often use depth-first approaches in determining the ideal move to take against an opponent. However, in enormous or infinite trees, a depth-first search may never terminate if we keep visiting subsequent child nodes.

Getting ready

We will traverse the following tree in a depth-first fashion. Starting at node r, we first explore...