Ticker

20/recent/ticker-posts

Tree Traversals

Traversing A Binary Tree 

  • Traversing a binary tree is the process of visiting each and every node in the tree exactly once in a systematic way.
  • As we know that a tree is a non-linear data structure in which the elements can be traversed in many different ways.

Types of traversals

  1. Pre-order Traversal
  2. In-order Traversal
  3. Post-order Traversal

Pre-order Traversal:-

  • To traverse a nonempty binary tree in pre-order, the following operations are performed at each node:
  1. Visiting the root node,
  2. Traversing the left sub-tree,
  3. Traversing the right sub-tree.
Pre-order Traversal

        Pre-order Traversal: 1 2 4 3  5 7 8 6
  • The pre-order traversal of the above tree is 1-2-4-3-5-7-8-6 as we have to traverse from root first, and then left sub-tree, and finally right sub-tree. 
  • Pre-order traversal is also called depth-first traversal.
  • The word 'pre' in the pre-order specifies that the root node is traversed first to any other nodes in the left and right sub-trees.
C++ code for pre-order traversal

//recursive function to perform pre-order traversal of the tree
void preorder(struct node *root)
{
        //if the current node is empty
if(root==NULL)
return;
        
         //display the data part of the root node.
cout<<root->data;

        //traverse the left sub-tree
preorder(root->left);

        //traverse the right sub-tree
preorder(root->right);
}

In-order Traversal:

  • To traverse a nonempty binary tree in in-order, the following operations are performed at each node:
  1. Traversing the left sub-tree,
  2. Visiting the root node,
  3. Traversing the right sub-tree.
In-order Traversal

                                                    In-order Traversal: 4 2 1 7 5 8 3 6

  • The in-order traversal of the above tree is 4-2-1-7-5-8-3-6.
  • Left sub-tree first, and then root node, and finally the right sub-tree.
  • In-order traversal is also called symmetric traversal.
  • The word 'in' in the in-order traversal specifies that the root node is accessed in between the left and the right sub-trees.
C++ code for in-order traversal

//recursive function to perform in-order traversal of the tree
void inorder(struct node *root)
{
        //if the current node is empty
if(root==NULL)
return;

         //traverse the left sub-tree
inorder(root->left);
        
         //display the data part of the root node.
cout<<root->data;

        //traverse the right sub-tree
inorder(root->right);
}

Post-order Traversal:

  • To traverse a nonempty binary tree in post-order, the following operations are performed at each node:
  1. Traversing the left sub-tree,
  2. Traversing the right sub-tree,
  3. Visiting the root node.
    Post-order Traversal

                       Post-order Traversal: 4 2 7 8 5 6 3 1

  • The post-order traversal of the above tree is 4-2-7-8-5-6-3-1.
  • Left sub-tree first, and then right sub-tree, and finally the root node.
  • In this traversal, the left sub-tree is always traversed before the right sub-tree and the root nodes.
  • The word 'post' in the post-order traversal specifies that the root node is accessed after the left and the right sub-trees.
C++ code for in-order traversal

//recursive function to perform post-order traversal of the tree
void postorder(struct node *root)
{
        //if the current node is empty
if(root==NULL)
return;

         //traverse the left sub-tree
postorder(root->left);

        //traverse the right sub-tree
postorder(root->right);
        
         //display the data part of the root node.
cout<<root->data;

}

So, we have come to the end of this article. I hope you guys liked this article.
Here are some articles you people may like:


Post a Comment

0 Comments