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