Tree traversals (preorder, postorder and  inorder)

Binary tree traversal refers to the process of visiting and processing each node in a binary tree exactly once in a systematic order. In a binary tree, each node has at most two child nodes, typically referred to as the left child and the right child. There are three common methods for traversing a binary tree:

1. Preorder traversal
2. Inorder traversal
3. Postorder traversal 

Preorder traversal

Following are the steps to be followed for preorder traversal:

• Visit the root node
• traverse the left sub-tree in pre-order
• traverse the right sub-tree in pre-order

Algorithm

Algorithm: Preorder Traversal

Step 1: If TREE is NULL, return.
Step 2: Write TREE -> DATA.
Step 3: Call PREORDER(TREE -> LEFT).
Step 4: Call PREORDER(TREE -> RIGHT).
Step 5: END.

Example:

Traverse the following binary tree by using pre-order traversal

• Since, the traversal scheme, we are using is pre-order traversal, therefore, the first element to be printed is 18.
• traverse the left sub-tree recursively. The root node of the left sub-tree is 211, print it and move to left.
• Left is empty therefore print the right children and move to the right sub-tree of the root.
• 20 is the root of sub-tree therefore, print it and move to its left. Since left sub-tree is empty therefore move to the right and print the only element present there i.e. 190.
• Therefore, the printing sequence will be 18, 211, 12, 20, 190.

Inorder Traversal

Following are the steps to be followed in Inorder traversal:

• Traverse the left sub-tree in in-order
• Visit the root
• Traverse the right subtree in in-order

Algorithm

Algorithm: Inorder Traversal

Step 1: If TREE is NULL, return.
Step 2: Call INORDER(TREE -> LEFT).
Step 3: Write TREE -> DATA.
Step 4: Call INORDER(TREE -> RIGHT).
Step 5: END.

Example:

Traverse the following binary tree by using in-order traversal.

• print the left most node of the left sub-tree i.e. 23.
• print the root of the left sub-tree i.e. 211.
• print the right child i.e. 89.
• print the root node of the tree i.e. 18.
• Then, move to the right sub-tree of the binary tree and print the left most node i.e. 10.
• print the root of the right sub-tree i.e. 20.
• print the right child i.e. 32.
• hence, the printing sequence will be 23, 211, 89, 18, 10, 20, 32.

Postorder Traversal

Following are the steps to be followed for Postorder traversal:

• Traverse the left sub-tree in post-order
• Traverse the right sub-tree in post-order
• visit the root

Algorithm

Algorithm: Postorder Traversal

Step 1: If TREE is NULL, return.
Step 2: Call POSTORDER(TREE -> LEFT).
Step 3: Call POSTORDER(TREE -> RIGHT).
Step 4: Write TREE -> DATA.
Step 5: END.

Example

Traverse the following tree by using post-order traversal

• Print the left child of the left sub-tree of binary tree i.e. 23.
• print the right child of the left sub-tree of binary tree i.e. 89.
• print the root node of the left sub-tree i.e. 211.
• Now, before printing the root node, move to right sub-tree and print the left child i.e. 10.
• print 32 i.e. right child.
• Print the root node 20.
• Now, at the last, print the root of the tree i.e. 18.
• The printing sequence will be 23, 89, 211, 10, 32, 20, 18.