Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.
There are three main traversals of the binary tree. Namely
- In-order traversal
- Post-order traversal
- Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.
In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.
For example consider the simple 3 node binary tree
In-order traversal: B A C
Post-order traversal: B C A
Pre-order traversal: A B C
To consider a bigger example, take the following binary search tree and it’s traversal sequences for the three algorithms.
In-order: 1 2 3 4 5 6 7 8
Post-order: 1 2 4 3 7 6 8 5
Pre-order: 5 3 2 1 4 8 6 7
The in-order traversal of the binary search tree always produces the sorted order of it’s elements.
Here is the C++ code for all the traversals.