A tree traversal
is a way of "visiting" every node in a tree. When you visit a node, you might do any of several things: draw the node, write its name into a string, set a parameter on the node, or something else depending on the algorithm you're trying to implement.
There are three standard orders for traversing a binary tree: preorder
, and postorder
. You can define each of these traversals recursively by writing code to decide what to do at each node.
In a preorder traversal, you visit the node and then visit its children recursively. It's called "preorder" because you visit a node pre- (before) visiting the children.
For example, consider the tree in Figure 2. This traversal outputs the node name—a letter in this case. You start the traversal at the root. The rule says to visit the node first so you output "A." Then you visit A's children.
To do that, you first visit node B and perform its preorder traversal. The rule says to visit the node first and then visit its children, so you output "B" and then move to node D. You output "D" and visit D's children. Finally, when you visit node H, you've reached a leaf, so you just output an "H." Normally you would visit the node's children but there aren't any, so this recursion ends and you move back up the tree to node D.
|Figure 3. Talented Traversal: In a preorder traversal, you visit a node first and then visit its children.|
Now that you've visited node H, you visit node D's other child: node I. Again, this is a root node so you output "I" and move back up to node D again. At this point you've visited node D and all its children, so that level of recursion ends and you move back up to node B.
From node B, you've already visited node D so you visit the other child: node E. The process continues like this until you have visited every node and output them all.
Figure 3 shows the tree from Figure 2 but with little numbers added showing the order in which a preorder traversal visits the nodes.
The final result of the preorder traversal is: A, B, D, H, I, E, J, K, C, F, L, G.
A postorder traversal is similar to a preorder traversal except that you visit a node's children before you visit the node itself. I'll leave it as an exercise for readers to verify that the postorder traversal for the tree in Figure 2 is: H, I, D, J, K, E, B, L, F, G, C, A.
The final type of traversal, an inorder traversal, is similar to the others except it always visits a node's left child, then the node itself, and finally, the node's right child. To be brief, the inorder traversal for the tree in Figure 2 is: H, D, I, B, J, E, K, A, L, F, C, G.