tree traversals

A tree traversal is an algorithm for visiting all the nodes (http://planetmath.org/Graph) in a rooted tree exactly once. The constraint is on rooted trees, because the root is taken to be the starting point of the traversal. A traversal is also defined on a forest in the sense that each tree in the forest can be iteratively traversed (provided one knows the roots of every tree beforehand). This entry presents a few common and simple tree traversals.

In the description of a tree (http://planetmath.org/forest), the notion of rooted-subtrees was presented. Full understanding of this notion is necessary to understand the traversals presented here, as each of these traversals depends heavily upon this notion.

In a traversal, there is the notion of visiting a node. Visiting a node often consists of doing some computation with that node. The traversals are defined here without any notion of what is being done to visit a node, and simply indicate where the visit occurs (and most importantly, in what order).

Examples of each traversal will be illustrated on the following binary tree.