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.

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.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.