Binary Search Tree

Write a Program to implement Binary Search tree as discussed in the Lecture.

The following methods are to be implemented in the Binary Search Tree.

 1)insert(key), function which inserts a new element into the tree. 

 2)remove(key), function which removes the key from the Binary Search Tree

    follow these conditions to while removing the element.

            

            i)if the tree-node having key is a leaf node, delete that node.

ii)replace the desired tree node with its child, if that node has only one child.

iii)If the tree node having key, has two non-empty children then use its 

inorder - predecessor to replace the node. Inorder - predecessor for a tree node is the right most node in its left subtree.

3)print(), print the elements of the tree in postorder, separate one element from another with a single whitespace.

You need to build a binary search tree by inserting elements in the given order.

Then perform insert and remove operations on that tree based on the operation specified as a character (i - insert, d - remove).

Input:

*1st line has number of elements to be added to the Binary Search Tree (Initial number  elements - N)

*2nd line of the input contains the elements each separated by single whitespace.

*3rd line has number of operations to be performed (k)

*4th line has operation, key separated by  a white space (i - insert, d - remove)

Output:

The program should output the post order traversal of BST after all the given operations are performed. Separate the elements with a single whitespace. Print “NULL”(without quotes), if the tree is empty.

Constraints:

Elements in the binary Search Tree are unique.

0<=N≤ 20

0<=key<=10000 (Elements in Tree)

0<=k<=10

#include <iostream>
using namespace std;
class binarySearchTree;
class treeNode{
	friend class binarySearchTree;
	private:
		int data;
		treeNode * left;
		treeNode * right;	
	public:
		treeNode(){
			left=right=NULL;
			//parent = NULL;
		}
		treeNode(int key){
			data=key;
			left=right=NULL	;
			//parent=NULL;
		}
		int getData(){ return data;}
		void setData(int key){data=key;}
};
class binarySearchTree{
	private:
		treeNode * root;
	public:
		binarySearchTree(){root=NULL;}
        void insert(int val)
        {
        	treeNode *ptr=root,*prev=root;
        	if(root==NULL)
        	{
        		root=new treeNode;
        		root->data=val;
        		root->right=NULL;
        		root->left=NULL;
        		return;
        	}
        	else
        	{
        		treeNode *temp;
			    temp=new treeNode;
        	    temp->data=val;
        	    temp->right=NULL;
        	    temp->left=NULL;
        	    while(ptr!=NULL)
        	    {
        		    prev=ptr;
        		    if(val>ptr->data)
        		    {
        		        ptr=ptr->right;
        		    }
        		    else if(val<ptr->data)
        		    {
        			    ptr=ptr->left;
        		    }
        	    }
                if(val<prev->data)
                {
              	    prev->left=temp;
                }
                else if(val>prev->data)
                {
                    prev->right=temp;
                }
            }
        }     
        void remove(int val)
        {
        	treeNode *ptr=root,*prev=root,*r,*p;
        	while(ptr->data!=val)
        	     {
        		    prev=ptr;
        		    if(val<ptr->data)
        		    {
        			    ptr=ptr->left;
        		    }
        		    else if(val>ptr->data)
        		    {
        			    ptr=ptr->right;
         		    }
        	     }
        	    if(ptr->left==NULL && ptr->right==NULL)
        	    {
        	    	if(prev->left==ptr)
        	    	{
        	    		prev->left=NULL;
        	    	}
        	    	else if(prev->right==ptr)
        	    	{
        	    		prev->right=NULL;
        	    	}
        	    	delete ptr;
        	    }
        	    else if(ptr->left==NULL)
        	    {
        	    	if(ptr->right->left!=NULL)
        	    	{
        	    		p=ptr->right;
        	    		r=ptr->right->left;
        	    		while(r->left!=NULL)
        	    		 {
        	    		 	p=r;
        	    		 	r=r->left;
        	    		 }
        	    		swap(ptr,r);
        	    		delete r;
        	    		p->left=NULL;
        	    	}
        	    	else
			{
				r=ptr->right->right;
				swap(ptr,ptr->right);
				delete ptr->right;
				ptr->right=r;
        	    	}
        	    }
        	    else
        	    {
        	    	if(ptr->left->right!=NULL)
        	    	{
        	    		p=ptr->left;
        	    		r=ptr->left->right;
        	    		while(r->right!=NULL)
        	    		{
        	    			p=r;
        	    			r=r->right;
        	    		}
        	    		swap(ptr,r);
        	    		delete r;
        	    		p->right=NULL;
        	    	}
        	    	else
        	    	{
        	    		r=ptr->left->left;
        	    		swap(ptr,ptr->left);
        	    		delete ptr->left;
        	    		ptr->left=r;
        	    	}
           	    }
   	    }
	    void print()
        {
                prnt(root);
        }
        void prnt(treeNode *ptr)
        {
        	if(root==NULL)
        	    cout<<"NULL";
        	if(ptr==NULL)
        	    return;
        	else
        	{
        		prnt(ptr->left);
        		prnt(ptr->right);
        		if(ptr==root)
        		cout<<ptr->data;
        		else
        		cout<<ptr->data<<" ";
        	}
        }
        treeNode *getRoot()
        {
        	return root;
        }
        void swap(treeNode *a,treeNode *b)
        {       
	        int temp=a->getData();
	        a->data=b->data;
	        b->data=temp;
        }
};
int main(){
	binarySearchTree bst;
	int N,val,k;
	char op;
	cin>>N;
	while(N--){
		cin>>val;
		bst.insert(val);
	}
	cin>>k;
	while(k--){
		cin>>op;
		cin>>val;

		if(op == 'i'){
			bst.insert(val);
		}
		else if (op=='d'){
			bst.remove(val);
		}
	}
	bst.print();
	return 0;
}