Now that we have seen how a binary tree is structured and doing a search operation over the same, lets look at how we can traverse over that data structure. There are three types of traversals that can be done.
- In-order traversal
- Pre-order traversal
- Post-order traversal
If you take a look at the above picture (yes, it looks a bit crowded, but you can track the numbers from 1 through twenty and the green ones are the values that we take), we start the process from the root and end up in the root. First search for the left most node. If there is none available take the immediate root and apply the same algorithm to the current node's right node. What i say may be a bit confusing but follow the numbers, you'l know.
Pre-order traversal follows the route VISIT ROOT / VISIT LEFT / VISIT RIGHT and the Post-order traversal follows the VISIT LEFT, VISIT RIGHT, VISIT ROOT.
For the above given example, the sequence that we get for various traversals is listed in the table below. You can cross-check it for yourself.
9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
50, 17, 9, 14, 12, 23, 19, 76, 54, 72, 67
12, 14, 9, 19, 23, 17, 67, 72, 54, 76, 50
In order traversal's application is clearly visible in this example (it gives a sorted list). Pre and post order traversals too have some powerful applications which we will look in the following posts.