Home » C++ programming language

Implement in-order traversal using C++ program



In this article, we are going to learn, how to implement in-order traversal using C++ program? This article contains different methods, algorithms and examples.
Submitted by Shubham Singh Rajawat, on July 24, 2017

In in-order traversal the left subtree is first then the root and later then right subtree i.e. in the order LNR (Left Node Right) where Node is the current node.

Here,
L(recursively traverse left subtree)
N(process node i.e. current root)
R(recursively traverse right subtree)

An in-order traversal can be done in two ways:

1. by recursive method

Algorithm:

inorder(root)
    a. Traverse the left subtree (inorder(root->left))
    b. visit the root
    c. Traverse the right subtree (inorder(root->right))

2. by non recursive method

This method is implemented by the use of stack.

a. create an empty stack
b. initialize current node as root node.
c. push current into the stack while current->left != NULL 
   update current as current=current->left
d. repeat while current is NULL and stack is not empty
    1. pop the element from the stack and update 
       current equal to the popped     element 
    2. print info of current
3.update current=current->right

C++ code to implement in-order traversal

#include<iostream>
#include<stack>
using namespace std;

/*structure to store a BST*/
struct node       
{
	int info;
	node *left,*right;
};

/*Method to create a newNode if a tree does not exist*/
node *newNode(int n)  
{
	node *ptr=new node;
	ptr->info=n;
	ptr->left=ptr->right=NULL;
	return ptr;
}

/*Method to insert given node in the BST */
node *insert(node* node,int info)  
{
	if(node==NULL)
	{
		return newNode(info);
	}
	if(info < node->info)          
	{
		node->left=insert(node->left,info);
	}
	else
	{
		node->right=insert(node->right,info);
	}
	return node;
}

/*Method to print inorder traversal of a BST*/
void inorder(node *root)             
{
	stack<node*> stack;
	node *curr=root; 
	while(!stack.empty() || curr!=NULL)
	{
		/*If current node is not NULL push the node in stack*/
		if(curr!=NULL)              
		{
			stack.push(curr);
			curr=curr->left;
		}
		/*If current node is empty or NULL pop it from the stack */
		else                        
		{
			curr=stack.top();
			stack.pop();
			cout<<curr->info<<" ";
			curr=curr->right;
		}
	}
}

//main program
int main()
{
	node* root=newNode(60);
	
	insert(root,50);
	insert(root,70);
	insert(root,40);
	insert(root,30);
	insert(root,80);
	insert(root,75);
	insert(root,65);
	insert(root,45);
	insert(root,55);
	insert(root,90);
	insert(root,67);
	
	cout<<"Inorder traversal :";
	/*Call/invoke statement for inorder method*/
	inorder(root);            
	
	cout<<endl;
	
	return 0;	
}

Output

Inorder traversal :30 40 45 50 55 60 65 67 70 75 80 90





Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.