### Preorder Traversal

The first depth-first traversal method we consider is called*preorder traversal*. Preorder traversal is defined recursively as follows. To do a preorder traversal of a general tree:

- Visit the root first; and then
- do a preorder traversal each of the subtrees of the root one-by-one in the order given.

- Visit the root first; and then
- traverse the left subtree; and then
- traverse the right subtree.

A,B,C,D,E,F,G,H,I

Notice that the preorder traversal visits the nodes of the tree in precisely the same order in which they are written in Equation . A preorder traversal is often done when it is necessary to print a textual representation of a tree.

### Postorder Traversal

The second depth-first traversal method we consider is*postorder traversal*. In contrast with preorder traversal, which visits the root first, postorder traversal visits the root last. To do a postorder traversal of a general tree:

- Do a postorder traversal each of the subtrees of the root one-by-one in the order given; and then
- visit the root.

- Traverse the left subtree; and then
- traverse the right subtree; and then
- visit the root.

C,B,F,G,E,I,H,D,A.

### Inorder Traversal

The third depth-first traversal method is*inorder traversal*. Inorder traversal only makes sense for binary trees. Whereas preorder traversal visits the root first and postorder traversal visits the root last, inorder traversal visits the root

*in between*visiting the left and right subtrees:

- Traverse the left subtree; and then
- visit the root; and then
- traverse the right subtree.

B,C,A,F,E,G,D,I,H.