Home » C++ programming language

Implement pre-order traversal using C++ program



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

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

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

A pre-order traversal can be done in two ways:

1. by recursive method

Algorithm:

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

2. by non recursive method

This method is implemented by the use of stack.

a. push the root into the stack
b. repeat while stack is not empty
    1. pop an node from the stack and print it
    2. push right child and then left child of the node into the stack 

C++ code to implement pre-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 preorder traversal of a BST*/
void preorder(node *root)             
{
	if(root == NULL)
	{
		return ;
	}
	
	stack<node*> stack;
	stack.push(root);
	while(!stack.empty())
	{
		node *curr=stack.top();
		cout<<curr->info<<" ";
		stack.pop();
		
		if(curr->right)
		{
			stack.push(curr->right);
		}
		if(curr->left)
		{
			stack.push(curr->left);
		}
	}
}
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<<"Preorder traversal :";
	/*Call/invoke statement for preorder method*/
	preorder(root);           
	
	cout<<endl;
	return 0;	
}

Output

Preorder traversal :60 50 40 30 45 55 70 65 67 80 75 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.