#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

struct Node
{
	int value;
	Node* left;
	Node* right;
	
	Node(int v) { value = v; left = right = NULL; }
};

class BST
{
private :
	Node* root;
	int size;

	Node* _Insert(Node* p , int x)
	{
		if ( p == NULL ) 
		{ 
			p = new Node(x);
			return p;
		}
		
		if ( x < p->value ) p->left  = _Insert( p->left , x );
		if ( x > p->value ) p->right = _Insert( p->right , x );
		return p;
	}
	
	void _Inorder(Node* p)
	{
		if (p == NULL) return ;
		
		_Inorder( p->left );
		cout<<p->value<<" ";
		_Inorder( p->right );
	}
	
	bool _Find(Node* p , int x)
	{
		if ( p == NULL ) return false;
		
		if ( p->value == x ) return true;
		if ( x < p->value ) return _Find( p->left , x );
		if ( x > p->value ) return _Find( p->right , x );
	}
	
	Node* _FindMin(Node* p)
	{
		while ( p->left != NULL )
			p = p->left;
		return p;
	}
	
	void _DeleteMin()
	{
		if ( root == NULL ) return;
		if ( root->left == NULL )
		{
			Node* p = root;
			root = root->right;
			delete p;
			return;
		}
	
		Node *p , *f;
		p = root;
		f = root->left;
		while ( f->left != NULL )
		{
			p = p->left;
			f = f->left;
		}
		p->left = f->right;
		delete f;
	}
	
public :
	BST() 
	{
		size = 0;
		root = NULL;
	}
	
	void Insert(int x)
	{
		root = _Insert(root , x);
	}
	
	void Inorder()
	{
		cout<<"Inorder : ";
		_Inorder( root );
		cout<<"\n";
	}
	
	bool Find(int x)
	{
		return _Find(root , x);
	}
	
	int FindMin()	// hadde aghal bayad ye ozv vujud dashte bashe
	{
		Node* f = _FindMin(root);
		return f->value;
	}
	
	void DeleteMin()
	{
		_DeleteMin();
	}
};

int main()
{
	BST b;
	
	b.Insert(5);
	b.Insert(3);
	b.Insert(12);
	b.Insert(8);
	
	b.Inorder();
	
	b.DeleteMin();
	b.Inorder();
	
	
	b.DeleteMin();
	b.Inorder();
	
	
	b.DeleteMin();
	b.Inorder();
	
	
	b.DeleteMin();
	b.Inorder();
	
	return 0;
}