Binary tree traversal

Binary tree traversal can be done in the following ways.

Inorder traversal
Preorder traversal
Postorder traversal

Consider the given binary tree,

         

Inorder Traversal: 7 9 4 2 5 1 3 6 8

Preorder Traversal: 1 2 4 7 9 5 3 6 8

Postorder Traversal: 9 7 4 5 2 8 6 3 1

Inorder Traversal: For binary search trees (BST), Inorder Traversal specifies the nodes in non-descending order. In order to obtain nodes from BST in non-increasing order, a variation of inorder traversal may be used where inorder traversal is reversed.

Preorder Traversal: Preorder traversal will create a copy of the tree. Preorder Traversal is also used to get the prefix expression of an expression.

Postorder Traversal: Postorder traversal is used to get the postfix expression of an expression given

Algorithm for binary tree traversal

Inorder(root)

Traverse the left sub-tree, (recursively call inorder(root -> left).
Visit and print the root node.
Traverse the right sub-tree, (recursively call inorder(root -> right).

Preorder(root)

Visit and print the root node.
Traverse the left sub-tree, (recursively call inorder(root -> left).
Traverse the right sub-tree, (recursively call inorder(root -> right).

Postorder(root)

Traverse the left sub-tree, (recursively call inorder(root -> left).
Traverse the right sub-tree, (recursively call inorder(root -> right).
Visit and print the root node.

Program for binary tree traversals in inorder, preorder, and postorder traversals is given below.

#include <iostream>
#include <stdlib.h>
using namespace std;

/* Structure for a node */
struct node
{
int data;
struct node *left;
struct node *right;
};

/* Function to create a new node */
struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

/* Function to insert a node in the tree */
void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case 'l' :root -> left = newNode(n2);
break;
case 'r' : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

/* Function to print the inorder traversal of the tree */
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << " ";
inorder(root -> right);
}

/* Function to print the preorder traversal of the tree */
void preorder(struct node *root)
{
if(root == NULL)
return;
cout << root -> data << " ";
preorder(root -> left);
preorder(root -> right);
}

/* Function to print the postorder traversal of the tree */
void postorder(struct node *root)
{
if(root == NULL)
return;
postorder(root -> left);
postorder(root -> right);
cout << root -> data << " ";
}

/* Main Function */
int main()
{
struct node *root = NULL;
int n;
cout <<"\nEnter the number of edges : ";
cin >> n;
cout << "\nInput the nodes of the binary tree in order \n\nparent-child-left(or)right-\n\n";
while(n--)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case 'l' :root -> left = newNode(n2);
break;
case 'r' : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout <<"\nInorder Traversal : ";
inorder(root);
cout << endl;
cout <<"\nPreorder Traversal : ";
preorder(root);
cout << endl;
cout <<"\nPostorder Traversal : ";
postorder(root);
cout << endl;
return 0;} 

output: