public class BinaryTree {

	protected BNode root;
	protected int size;
	
	/**Creates an empty binary tree. */
	public BinaryTree(){
		root=null;
		size=0;
	}
	
	/**Returns the number of nodes in the tree. */
	public int size(){
		return size;
	}
	
	/**Returns whether the tree has any nodes or not. */
	public boolean isEmpty(){
		return (size==0);
	}
	
	/**Returns the root of the tree. */
	public BNode root(){
		return root;
	}
	
	/**Returns the parent of a given node. */
	public BNode parent(BNode p){
		return p.getParent();
	}
	
	/**Returns the left child of a given node. */
	public BNode leftChild(BNode p){
		return p.getLeftChild();
	}
	
	/**Returns the right child of a given node. */
	public BNode rightChild(BNode p){
		return p.getRightChild();
	}
	
	/**Returns the object stored in a given node. */
	public Object element(BNode p){
		return p.getElement();
	}
	
	/**Returns whether a given node is internal. */
	public boolean isInternal(BNode p){
		return hasLeft(p)||hasRight(p);
	}
	
	/**Returns whether a given node is external.*/
	public boolean isExternal(BNode p){
		return  !hasLeft(p)&&!hasRight(p);
	}
	
	/**Returns whether a given node is the root of the tree. */
	public boolean isRoot(BNode p){
		return p.getParent()==null;
	}
	
	/**Replace the element at a node. */ 
	public Object replace(BNode p, Object o){
		Object temp=p.getElement();
		p.setElement(o);
		return temp;
	}
	
	/**Returns whether a node has a left child. */
	public boolean hasLeft(BNode p){
		return p.getLeftChild()!=null;
	}
	
	/**Returns whether a node has a right child. */
	public boolean hasRight(BNode p){
		return p.getRightChild()!=null;
	}
	
	/**Adds a root node to an empty tree. */
	public BNode addRoot(Object ele){
		if(!isEmpty()){
			System.out.println("Tree already has a root.");
			return null;
		}
		size=1;
		root=new BNode(ele,null,null,null);
		return root;
	}
	
	/**Inserts a left child at a given node. */
	public BNode insertLeft(BNode p,Object ele){
		if(hasLeft(p)){
			System.out.println("Node already has a left child.");
			return null;
		}
		BNode left=new BNode(ele,p,null,null);
		p.setLeftChild(left);
		size++;
		return left;
	}
	
	/**Inserts a right child at a given node. */
	public BNode insertRight(BNode p,Object ele){
		if(hasRight(p)){
			System.out.println("Node already has a right child.");
			return null;
		}
		BNode right=new BNode(ele,p,null,null);
		p.setRightChild(right);
		size++;
		return right;
	}
	
	/**delete a leaf node of the binary tree*/
	public Object deleteLeaf(BNode p){
		if(!isExternal(p)){
			System.out.println("The node is not a leaf");
			return null;
		}
		BNode parent=parent(p);
		if(p==leftChild(parent)){
			parent.setLeftChild(null);
		}
		else if(p==rightChild(parent)){
			parent.setRightChild(null);
		}
		size--;
		return p.getElement();
	}
}


class BNode{
	private Object element;
	private BNode parent,leftChild,rightChild;
	
	public BNode(){
		this(null,null,null,null);
	}
	
	 /** Creates a node with the given element, parent,left child and right child. */
	public BNode(Object ele, BNode p, BNode left, BNode right){
		parent=p;
		element=ele;
		leftChild=left;
		rightChild=right;
	}
	
	/**Accessor methods: */
	public Object getElement(){
		return element;
	}
	public BNode getParent(){
		return parent;
	}
	public BNode getLeftChild(){
		return leftChild;
	}
	public BNode getRightChild(){
		return rightChild;
	}
	
	/**Modifier methods: */
	public void setElement(Object ele){
		element=ele;
	}
	public void setParent(BNode p){
		parent=p;
	}
	public void setLeftChild(BNode left){
		leftChild=left;
	}
	public void setRightChild(BNode right){
		rightChild=right;
	}
	
}