# 2. Tree Traversal

What I've just called ``scanning through'' a tree is actually called traversing a tree.

General Definition: to traverse a data structure is to process, however you like, every node in the data structure exactly once.

Note: You may ``pass through'' a node as many times as you like but you must only process the node once.
E.g. we can talk about ``traversing a list'', which means going through the list and processing every node once. We had a special name for this: `map`.

For a specific data structure, we talk about the different orders in which it might be traversed. For a list there are two common traversal orders: first-to-last (the most common) and last-to-first.

The general recursive pattern for traversing a (non-empty) binary tree is this: At node N you must do these three things:

• (L) recursively traverse its left subtree. When this step is finished you are back at N again.

• (R) recursively traverse its right subtree. When this step is finished you are back at N again.

• (N) Actually process N itself.
We may do these things in any order and still have a legitimate traversal. If we do (L) before (R), we call it left-to-right traversal, otherwise we call it right-to-left traversal.
Pre-Order Traversal
do (N) before anything else.
Post-Order Traversal
do (N) after everything else.
In-Order, or Infix Order, Traversal
do (N) in between the two subtrees.
E.g. let us look at what order the nodes will get processed given this tree:
`        `
Using Left-To-Right traversal:
`        `

For example, suppose we were writing out the nodes of the tree:

```        void print_tree(binary_tree *t)
{
if (! is_empty(t)) {
print_tree(t->left);     /* L */
print_tree(t->right);    /* R */
printf("%d\n",t->value); /* N */
}
}```
The preceding diagrams show us the order in which the nodes will get written:
• Pre-Order: A-B-D-C-E-F
• In-Order: B-D-A-E-C-F
• Post-Order: D-B-E-F-C-A