Algorithm for Traversal of a Binary Tree (Inorder, Preorder and Postorder)

Algorithm for in-order traversal

Step 1: Repeat Steps 2 to 4 while TREE != NULL 
Step 2: INORDER(TREE LEFT) 
Step 3: Write TREE DATA 
Step 4: INORDER(TREE RIGHT) [END OF LOOP] 
Step 5: END

Explanation

  • The in-order traversal of the tree is given as B, A, and C.
  • Left sub-tree first, the root node next, and then the right sub-tree.
  • In-order traversal is also called as symmetric traversal.
  • In this algorithm, the left sub-tree is always traversed before the root node and the right sub-tree.
  • The word ‘in’ in the in-order specifies that the root node is accessed in between the left and the right sub-trees.
  • In-order algorithm is also known as the LNR traversal algorithm (Left-Node-Right).
  • In-order traversal algorithm is usually used to display the elements of a binary search tree.

Algorithm for pre-order traversal

Step 1: Repeat Steps 2 to 4 while TREE != NULL 
Step 2: Write TREE DATA 
Step 3: PREORDER(TREE LEFT) 
Step 4: PREORDER(TREE RIGHT) [END OF LOOP] 
Step 5: END

Explanation

  • The pre-order traversal of the tree is given as A, B, C.
  • Root node first, the left sub-tree next, and then the right sub-tree.
  • Pre-order traversal is also called as depth-first traversal. In this algorithm, the left sub-tree is always traversed before the right sub-tree.
  • The word ‘pre’ in the pre-order specifies that the root node is accessed prior to any other nodes in the left and right sub-trees.
  • Pre-order algorithm is also known as the NLR traversal algorithm (Node-Left-Right).
  • Pre-order traversal algorithms are used to extract a prefix notation from an expression tree.

Algorithm for post-order traversal

Step 1: Repeat Steps 2 to 4 while TREE != NULL 
Step 2: POSTORDER(TREE LEFT) 
Step 3: POSTORDER(TREE RIGHT) 
Step 4: Write TREE DATA [END OF LOOP] 
Step 5: END

Explanation

  • The post-order traversal of the tree is given as B, C, and A.
  • Left sub-tree first, the right sub-tree next, and finally the root node.
  • In this algorithm, the left sub-tree is always traversed before the right sub-tree and the root node.
  • The word ‘post’ in the post-order specifies that the root node is accessed after the left and the right sub-trees.
  • Post-order algorithm is also known as the LRN traversal algorithm (Left-Right-Node).
  • Post-order traversals are used to extract postfix notation from an expression tree.