# Binary Tree Traversal

Binary Tree Traversal is a process of visiting every node of the tree and print the node value. Unlike linear data structure like arrays and linked lists which can be traversed only in linear manner. Trees can be traversed in multiple manner.

Majorly, the trees can be traversed in following three manners:

Preorder Traversal:

The Preorder traversal uses following traversal algorithm to traverse the tree.

• Visit the Root.
• Visit the Left Subtree.
• Visit the Right Subtree.

Application of Preorder Traversal:

• Preorder traversal is used to create copy of the tree.
• Preorder traversal is also used to generate prefix expression of an expression tree.

Inorder Traversal:

The Inorder Traversal uses following traversal algorithm to traverse the tree.

• Visit the Left Subtree.
• Visit the Root.
• Visit the Right Subtree.

Application of Inorder Traversal:

• Inorder tree traversal can be used to check whether tree is binary search tree or not.
• Inorder tree traversal is used to generate infix expression of expression tree.

Postorder Traversal:

The Postorder Traversal uses following traversal algorithm to traverse the tree.

• Visit the Left Subtree.
• Visit the Right Subtree.
• Visit the Root.

Application of Postorder Traversal:

• Postorder tree traversal is used to delete the tree. Here, leaves are deleted then respective roots.
• Postfix Traversal is also used to generate Postfix expression of expression tree.

Implementation of Tree Traversals:

Tree Traversals can be implemented in 3-manners:

1. Using Recursion.
2. Using Stack Data Structure.
3. Using Morris Algorithm.

Here, in this post, we will implement the preorder, inorder and postorder tree traversals using recursion.

#### C++ Program to Implement Binary Tree Traversal is as follows:

```/* C++ Program to Implement Binary Tree Traversal */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to Implement Preorder Traversal */
void preorder(Node *root)
{
if(root == NULL)
return;

cout<<root->data<<" ";

preorder(root -> left);

preorder(root -> right);
}

/* Function to Implement Inorder Traversal */
void inorder(Node *root)
{
if(root == NULL)
return;

inorder(root -> left);

cout<<root->data<<" ";

inorder(root -> right);
}

/* Function to Implement Postorder Traversal */
void postorder(Node *root)
{
if(root == NULL)
return;

postorder(root -> left);

postorder(root -> right);

cout<<root->data<<" ";
}
int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);

/* Traversing Tree in Preorder, Inorder and Postorder Form */

/* Preorder Traversal */
cout<<"The Preorder Traversal is:\n";
preorder(root);
cout<<endl;

/* Inorder Traversal */
cout<<"The Inorder Traversal is:\n";
inorder(root);
cout<<endl;

/* Postorder Traversal */
cout<<"The Postorder Traversal is:\n";
postorder(root);
cout<<endl;
}

```

OUTPUT:

```The Preorder Traversal is:
1 2 4 5 3 6 7
The Inorder Traversal is:
4 2 5 1 6 3 7
The Postorder Traversal is:
4 5 2 6 7 3 1```

Related Posts: