__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__

**Pre-order Traversal****In-order Traversal****Post-order Traversal**

__Pre-order Traversal:-__

- To traverse a nonempty binary tree in pre-order, the following operations are performed at each node:

- Visiting the
*root node,* - Traversing the
*left sub-tree,* - Traversing the
*right sub-tree.*

*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:

- Traversing the
,*left sub-tree* - Visiting the
*root node,* - Traversing the
*right sub-tree.*

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:

- Traversing the
,*left sub-tree* - Traversing the
,*right sub-tree* - Visiting the
*root node.*

**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:

## 0 Comments