Traversals

Traversals

Definition:

Tree traversal refers to the process of visiting every node of a tree data structure exactly once in a specific order.

Since trees are non‒linear, traversals provide a systematic way to access all nodes. For these traversals we will use some notations as follows:

L means move to the left child.

R means move to the the right child.

D means the root/parent node.

Now, with this L, R, D one can have six different combinations of L, R, D nodes. Such as LDR, LRD, DLR, DRL, RLD, RDL. But from computing point of view we will have three different ways of traversing a tree. Those three combinations will be LDR, DLR, LRD. Those are called Inorder, Preorder and Postorder traversals.

Common traversal techniques :

1. Inorder traversal :

C‒B‒A‒D‒E is the inorder traversal i.e. first we go towards the leftmost node i.e. C so print that node C. Then go back to the node B and print B. Then root node A then move towards the right sub‒tree print Print D and finally E. Thus we are following the tracing sequence of LDR. This type of traversal is called inorder traversal. The basic principal is to traverse left sub‒tree then root and then the right sub‒tree.

2. Preorder traversal :

 A‒B‒C‒D‒E is the preorder traversal of the Fig. 6.4.2. We are following DLR path. i.e. data at the root node will be printed first then we move on the left sub‒tree and  go on printing the data till we reach to the leftmost node. Print the data at that node and then move to the right subtree. Follow the same DLR principle at each sub‒tree and go on printing the data accordingly.

3. Postorder traversal :

From Fig. 6.4.3 the postorder sequence isod C‒D‒B‒E‒A. In the postorder traversal we are following the LRD principle i.e. move to the leftmost node check if right sub‒tree is there or not if not then print the leftmost node, if right subtree is there move towards the rightmost node. The key idea here is that at each sub‒tree we are following the LRD principle and print the data accordingly.

1. Recursive inorder traversal

Algorithm :

If tree is not empty then

a. Traverse the left sub‒tree in inorder.

b. Visit the root node.

c. Traverse the right sub tree in inorder.

The recursive routine for inorder traversal is as given below.

void _TREE CLASS::inorder(node *temp)

{

   if(temp!=NULL)

   {

      inorder(temp‒>left);<‒‒‒‒‒‒‒‒‒‒‒‒Moving to leftmost node

      cout<<" "<<<temp‒>data;

      inorder(temp‒>right);<‒‒‒‒‒‒‒‒‒‒‒Moving to rightmost node

   }

}

2. Recursive preorder traversal

Algorithm :

If tree is not empty then

a. Visit the root node.

b. Traverse the left sub‒tree in preorder.

c. Traverse the right sub‒tree in preorder.

The recursive routine for preorder traversal is as given below.

void TREE_ CLASS::preorder(node *temp)

{

   if(temp!= NULL)

   {

      cout<<""<<<temp‒>data;

      preorder(temp‒>left);

      preorder(temp‒>right);

   }

}

 

3. Recursive postorder traversal

Algorithm :

If tree is not empty then

a. Traverse the left sub‒tree in postorder.

b. Traverse the right sub‒tree in postorder.

c. Visit the root node.

The recursive routine for postorder traversal is as given below.

void TREE_ CLASS::postorder(node *temp)

{

   if(temp!=NULL)

   {

   postorder(temp‒>left);

   postorder(temp‒>right);

   cout<<" "<<temp‒>data;

 }

}

 

Example : 1

Traverse the tree given below using inorder, preorder and postorder traversals.

Solution :

Inorder : D H B E A F C I G J

Preorder : A B D H E C F G I J

Postorder : D H E B F I J G C A

 

Example : 2

Write an algorithm to traverse binary tree level by level, with each level of the tree being traversed from left to right.

Solution: Algorithm

1. Start by visiting the root node.

2. Insert the node in a queue then insert one dummy node in the queue. This dummy node is used as a mark for change in the level.

3. Delete the node.

3 (a) If the deleted node is not a dummy node then print its data and insert its left node (if exists) in the queue, then insert the right node (if exists) in the queue.

3 (b) Else insert the dummy node. Then go to a new line, so that the contents of next level gets printed on the new line.

4. Repeat step 3 until the queue is not empty.

 

The pseudo C algorithm is as given below ‒

void tree::display()

{

dummy = new btree;

if ( dummy = = NULL)

cout<<"Insufficient Memory\n";

dummy‒>left = root;

dummy‒>right = NULL;

dummy‒>data = ' ';

temp = dummy ‒>left;

enque(temp); //inserting the node in the queue

enque(dummy);

temp = deque();//deleting the node from the queue

while (front != rear)

{

   if ( temp != dummy)

   {

      cout<<" "<<temp‒>data;

      if ( temp ‒>left != NULL)

          enque(temp ‒> left);

      if (temp‒>right != NULL)

          enque(temp ‒> right);

   }

   else

   {

      enque(temp);

      cout<<"\n";

   }

temp = deque();

}

}

Review Questions

1. Describe briefly the various tree traversals.

2. Discuss the different methods traversing a binary tree with algorithm.