public class BinarySearchTree
{
 
	private class node
	{
		int data;
		node leftchild;
	     node rightchild;
	}
 
   	public BinarySearchTree()
	{ //create an empty Binary Search Tree }
//node root = new node;
root=null;
 
	}
 
 
   	public boolean empty()
{ // return true if the tree is empty, otherwise return false }
 if ( root == null ){
 return true;
 }else{
 return false;
 }
 
}
   	public void Insert(int x)
{//insert a value x }
  //search for a location to insert
  node p=root; 
  node q=null;
  while(p!=null){
   q=p;
   if(x == p.data){ return;
 }  
	if(x < p.data){ p=p.leftchild;
   }else{ p=p.rightchild;
 }
}
// create the new node
  p=new node();
  p.data = x;
  p.leftchild = p.rightchild = null;
//attaching the new node to the tree
  if(root==null){ root = p;
  }else if(x < q.data){ q.leftchild=p;
  }else{ q.rightchild = p;
  }
  return;
  }
public void Delete(int x)
{//if value x is in the tree, remove x }
 
//make node for q and p
node q = new node();
node p = new node();
q=p=root;
 
while(q==null)
{
if(x==p.data)
break;
q=p;
if(x < p.data)
p = q.leftchild;
else
p=p.rightchild;
}
if(p!=null){
p=p.rightchild;
}
}
 
public void Display()
{// Display the data values from smallest to largest }
 Display (root); 
}
public void Display(node p) 
{ 
	if(p!= null){ 
		Display(p.leftchild); 
		System.out.println(p.data); 
		Display(p.rightchild); 
	} 
}
 
 
   	private node root;//pointer to the root node 
}
 
----------------MAIN------------------------------------------------ 
 
public class BinarySeachtreeMain{
public static void main(String[] arg)
{
    BinarySearchTree X = new BinarySearchTree();
 
X.Insert(50);
    	X.Insert(10);
    	X.Insert(20);
	X.Insert(80);
	X.Insert(60);
	X.Insert(30);
 
     	X.Display();
 
 
 
 
     X.Delete (20);
     System.out.println ("Tree after deleting 20:");
     X.Display();
     X.Delete(50);
     System.out.println ("Tree after deleting 50:");
     X.Display();
 
     if(!X.empty())
	System.out.println("Tree is not empty.");
}     
}