Comparing Traversal Methods
When working with binary tree data structures, we often want to quickly sketch in our minds what a particular approach's traversal sequence looks like. Having this sketch can be a powerful tool for gainign some traction on solving a problem. Accordingly, let's investigate some techniques for quickly determining a particular sequence.
First, it's helpful to associate the traversal approaches with a few visit
sequences. For the visit sequences in the table below, L stands for
"visit the left subtree," root stands for "visit the root," and R
stands for "visit the right subtree."
| Preorder | root L R |
|---|---|
| Inorder | L root R |
| Postorder | L R root |
| Generational | Generation by generation, left to right |
Knowing these sequences can make traversal sequences for more complicated trees clearer. For example, consider the following tree:
Trying to determine the traversal sequence for any given traversal approach can appear daunting. The trick, however, is divide and conquer: Break the tree down into subtrees. In this case, let's break it down into a left-subtree (the nodes in red) and a right-subtree (the nodes in blue):
Let's first consider preorder traversal. For preorder traversal, we have
root L R. So, we write:
Now we fill in the parentheses. First, the left subtree, following the same
sequence, root L R:
Then the right subtree, following the same sequence, root L R.
Thus, the inorder traversal sequence for the tree is:
Using the same method, let's try inorder traversal. For inorder traversal,
the visit sequence is L root R. So we write:
Now we fill in the subtree parentheses. Starting with the left subtree, we
use the same sequence, L root R:
Then we fill in the right subtree's parentheses, again using L root R:
Hence, the inorder traversal sequence is:
Now let's try postorder traversal. The visit sequence is L R root, so we
have:
Now we fill in the subtrees, again using L R root. For the left subtree:
And for the right subtree:
This yields the postorder traversal sequence:
Finally, generational traversal is simple enough that we don't need to apply some visit sequence. We merely traverse the tree from the first generation to the last generation, visiting each node from left to right: