C++ program that uses non-recursive functions to traverse a binary tree in Pre-order

/* Write C++ program that uses non-recursive functions to traverse a binary tree in Pre-order */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
 
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
	node *temp,*temp1;
	if(root== NULL)
	{
		root=new node;
		root->data=ch;
		root->left=NULL;
		root->right=NULL;
		return;
	}
	temp1=new node;
	temp1->data=ch;
	temp1->right=temp1->left=NULL;
	temp=search(root,ch);
	if(temp->data>ch)
		temp->left=temp1;
	else
		temp->right=temp1;
 
}
 
node *search(node *temp,int ch)
{
	if(root== NULL)
	{
		cout <<"no node present";
		return NULL;
	}
	if(temp->left==NULL && temp->right== NULL)
		return temp;
 
	if(temp->data>ch)
	     {  if(temp->left==NULL) return temp;
		search(temp->left,ch);}
	else
	      { if(temp->right==NULL) return temp;
	      search(temp->right,ch);
 
}              }
 
void display(node *temp)
{
	if(temp==NULL)
	 return ;
	display(temp->left);
       cout<<temp->data <<" ";
	display(temp->right);
}
void preorder( node *root)
{
	node *p,*q;
	p=root;
	q=NULL;
	top=0;
 
	while(p!=NULL)
	{
		cout <<p->data  << " ";
		if(p->right!=NULL)
		{
			stk[top]=p->right->data;
			top++;
		}
		p=p->left;
		if(p==NULL && top>0)
	{
		p=pop(root);
	}
	}
}
 
node * pop(node *p)
{
int ch;
ch=stk[top-1];
if(p->data==ch)
{
top--;
return p;
}
if(p->data>ch)
pop(p->left);
else
pop(p->right);
}
};
main()
{
	tree t1;
	int ch,n,i;
	while(1)
	{
		cout <<"\n1.INSERT\n2.DISPLAY 3.PREORDER TRAVERSE\n4.EXIT\nEnter your choice:";
		cin >> ch;
		switch(ch)
		{
		case 1:   cout <<"enter no of elements to insert:";
			  cout<<"\n enter the elements";
			  cin >> n;
			  for(i=1;i<=n;i++)
			  {  cin >> ch;
			     t1.insert(ch);
			  }
			   break;
		case 2:   t1.display(t1.root);break;
		case 3:   t1.preorder(t1.root); break;
		case 4:   exit(1);
		}
	}
}

OUTPUT

1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:1
enter no of elements to insert
enter the elements7
5 24 36 11 44 2 21

1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:2
2 5 11 21 24 36 44

Start exploring endless computing possibilities with your own Raspberry Pi computer and accessories. Perfect for beginners and students.

1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:3
5 2 24 11 21 36 44

1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:4


2 Responses to “C++ program that uses non-recursive functions to traverse a binary tree in Pre-order”

  1. ur enemy

    plz give definition for non-recursive.
    after then give example programs ok

    Reply
  2. Hey, I agree the number of itoaetirns will be greater than n but the total number of itoaetirns shall still be some constant factor of n, in fact it will be actually bounded by 2*n.I am actually printing the nodes as would have been printed in pre-order traversal of the tree. The logic is that from a given node A, go down in the left subtree of this node A (applying the same logic at each node reached in the subtree) as you can go and then come back to this node A and do the same in the right subtree (applying the same logic at each node reached in the subtree) and then again come back to this node and transfer the control to parent of this current node A.So, the number of itoaetirns used for traversing down the left sub-tree would be same as the number of itoaetirns in traversing up back to the node and hence it would be bound by a factor of 2*n, overall. Hope, you were able to follow the logic. If you try running an example using the code present here and print the number of itoaetirns for your sample data, you shall get a more clear picture of the logic.

    Reply

Leave a Reply