Computer Organization

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:

Example 01 tree traversal

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:

Example 02 tree traversal

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

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest