Preorder Traversal

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

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.

Preorder traversal gets its name from the fact that it visits the root first. In the case of a binary tree, the algorithm becomes:

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

For example, a preorder traversal of the tree shown in Figure

visits the nodes in the following order:

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.