Tree Traversals And Its Types

Reading/Processing the data of a node exactly once in the some order in a tree. The following ways are generally used for traversing a tree.

There are two major types of Tree Traversals

1. Depth first

   I. Preorder Traversal
   II. Inorder Traversal
   III. Postorder Traversal

2. Breadth-First or Level Order Traversal

1. Depth-first

I. Preorder Traversal (Algorithm)

• Visit the root.  
• Traverse the left subtree, i.e., call Preorder(left-subtree)  
• Traverse the right subtree, i.e., call Preorder(right-subtree)

II. Inorder Traversal (Algorithm)

• Traverse the left subtree, i.e., call Inorder(left-subtree)
• Visit the root.
• Traverse the right subtree, i.e., call Inorder(right-subtree)

III. Postorder Traversal (Algorithm)

• Traverse the left subtree, i.e., call Postorder(left-subtree)
• Traverse the right subtree, i.e., call Postorder(right-subtree)
• Visit the root.

2. Level Order Traversal

Traverse In the tree through level by level. i.e. start from node (level 1) and then level 2 and so on…

Explain Through Example

Example 01:

Depth first

• Inorder: 4,2,5,1,3
• Pre-order: 1,2,4,5,3
• Post order: 4,5,2,3,1

Breadth-First or Level Order Traversal: 1,2,3,4,5

Example 2:

Depth first

• InOrder: 4,10,12,15,18,22,24, 26, 31, 35, 44, 50, 66, 60, 90
• Pre-order: 26, 15,10,4,12,22,18,24,50,35,31,44,70,66,90
• Post-order: 4, 12,10,18,24,22,15,31,44,35,66,90,70,50,25

Breadth First or Level Order Traversal: 26,15,50,1022,35,70, 4, 12, 18, 24, 31,44,66,90