Binary Tree Traversals in C++

In this tutorial, we will learn Binary tree traversals in C++. Three standard ways to traverse a binary tree T with root R are preorder, inorderpostorder, are as follows:

Preorder:

  1. Process root R.
  2. Travel in the left subtree of R in preorder.
  3. Travel in the right subtree of R in preorder.

Inorder:

  1. Travel in left subtree of R in inorder.
  2. Process root R.
  3. Travel in right subtree of R in inorder.

Postorder:

  1. Travel in left subtree of R in postorder.
  2. Travel in right subtree of R in postorder.
  3. Process  root R.

The three algorithm are sometimes called , respectively , the node-left-right(NLR) traversal ,the left-node-right(LNR) traversal and the left-right-root(LRN) traversal.

You may also learn:

Program: Perform Binary Tree Traversals in C++

Below is the C++ Code to perform the mentioned operation.

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

struct st
{
int data;
struct st *left;
struct st *right;
};
struct st *root=NULL,*temp;
void insertElements();
void preorder(struct st *);
void inorder(struct st *);
void postorder(struct st *);
int main()
{
 int ch;

 while(1)
 {
 cout<<"\n 1.insert Elements \n 2.preorder \n 3.inorder \n 4.postorder \n5.exit";
  cout<<"\n enter ur choice ";
  cin>>ch;
  switch(ch)
  {
   case 1:insertElements();break;
   case 2:preorder(root);break;
   case 3:inorder(root);break;
   case 4:postorder(root);break;
   case 5:exit(1);break;
   default:cout<<"invalid operation";

  }
 }
}
void insertElements()
{
struct st *nc,*pNode;
int v;
cout<<"\n enter the value ";
cin>>v;
temp=new st;
temp->data=v;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
{
root=temp;
}
else
{
nc=root;
while(nc!=NULL)
{
pNode=nc;
if(v<nc->data)
nc=nc->left;
else
nc=nc->right;
}
if(v<pNode->data)
{
pNode->left=temp;
}
else
pNode->right=temp;
}
}
void preorder(struct st *temp)
{
if(temp!=NULL)
{
                cout<<" "<<temp->data;
                preorder(temp->left);
                preorder(temp->right);
}
}
void inorder(struct st *temp)
{
                if(temp!=NULL)
{
                inorder(temp->left);
                cout<<" "<<temp->data;
                inorder(temp->right);

}
}
void postorder(struct st *temp)
{
                if(temp!=NULL)
                {
                                postorder(temp->left);
                                postorder(temp->right);
                                cout<<" "<<temp->data;
                }
}

Output:

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your choice 1

 enter the value 5

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your choice 1 

 enter the value 1

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your  choice 1

 enter the value 3

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your  choice 1

 enter the value 2

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your  choice 1

 enter the value 4

 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your choice 2
 5 1 3 2 4
 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your choice 3
 1 2 3 4 5
 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your choice 4
 2 4 3 1 5
 1.insert Elements
 2.preorder
 3.inorder
 4.postorder
 5.exit
 enter your  choice 5

Leave a Reply

Your email address will not be published. Required fields are marked *