In-order Traversal
In this traversal method, the left sub-tree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a sub-tree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.
We start from A, and following in-order traversal, we move to its left sub-tree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of in-order traversal of this tree will be −
D → B → E → A → F → C → G
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left sub-tree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right sub-tree.
Pre-order Traversal
In this traversal method, the root node is visited first, then the left sub-tree and finally the right sub-tree.
We start from A, and following pre-order traversal, we first visit A itself and then move to its left sub-tree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be −
A → B → D → E → C → F → G
Algorithm
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left sub-tree.
Step 3 − Recursively traverse right sub-tree.
Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left sub-tree, then the right sub-tree and finally the root node.
We start from A, and following Post-order traversal, we first visit the left sub-tree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be −
D → E → B → F → G → C → A
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left sub-tree.
Step 2 − Recursively traverse right sub-tree.
Step 3 − Visit root node.
