﻿ Algorithm for Traversal of a Binary Tree (Inorder, Preorder and Postorder) || CseWorld Online

# 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.