Traversals in a binary search tree in Java

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.

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

In-order traversal follows the route VISIT LEFT / VISIT ROOT / VISIT RIGHT. For a given binary tree, first visit the left most node and if no left node exists, visit the root and then visit the right. By this fashion traversal can be done. As a matter of fact, a simple In-order traversal in a binary search tree would give the sorted result! How cool is that!?

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.

Order	Sequence
In-order	9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
Pre-order	50, 17, 9, 14, 12, 23, 19, 76, 54, 72, 67
Post-order	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.

Cheers,
Bragaadeesh.