There are three main traversals of the binary tree. Namely
- In-order traversal
- Post-order traversal
- Pre-order traversal
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
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.