Answer to Question #268106 in C++ for Myname

Question

Write a program to implement a binary search tree (BST) having following functionalities.

 BSTInsert(): This function adds a given ITEM to the BST. If the ITEM already exists in the BST then it

will not insert the ITEM any more.

 BSTInorderStack(): This function finds Inorder traversal sequence of a BST using stack. You are not

supposed to use recursive implementation of Inorder traversal

Answer 1

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

struct Node
{
	int data;
	struct Node *right;
	struct Node *left;
	Node(int _data):data(_data),left(NULL),right(NULL){}
};

class BST
{
public:
	//Function for insertion new node to the BST
	struct Node* BSTInsert(int value, Node* p)
	{
		if(p==NULL)
		{
			p=new Node(value);
		}
		else if(value<p->data)
		{
			p->left=BSTInsert(value,p->left);
		}
		else if(value>p->data)
		{
			p->right=BSTInsert(value,p->right);
		}
		return p;	
	}
	
	void BSTInorderStack(Node* root)
	{
		stack<Node*>st;
		Node* temp=root;
		while(temp!=NULL||!st.empty())
		{
			while(temp!=NULL)
			{
				//Add element to stack and check left Node
				st.push(temp); 
				temp=temp->left;
			}
			temp=st.top();
			//Print top element of stack
			cout<<temp->data<<" ";
			//Delete top element of stack
			st.pop();
            //Find right element
			temp=temp->right;			
		}
	}
};

int main()
{
	BST bs;
	//Make BST  
	Node *root=new Node(10);
	bs.BSTInsert(7,root);
	bs.BSTInsert(8,root);
	bs.BSTInsert(5,root);
	bs.BSTInsert(13,root);
	//Do a repeat of 5 on purpose
	bs.BSTInsert(5,root);
	bs.BSTInsert(15,root);
	/*Binary tree is
			10
		   /  \
		  7   13
		/  \	\
	   5    8	15
	 Inorder output must be 5 7 8 10 13 15 
	*/
	bs.BSTInorderStack(root);
	
}