import java.util.*;

public class BinaryTree {
	
   class TreePosition{
		Object element;
		TreePosition parent;
		TreePosition leftChild;
		TreePosition rightChild;
		
		public Object element(){
			return this.element;
		}
	}
		
	TreePosition root;
	int n;
	
	public BinaryTree(){
		this.root = null;
		this.n = 0;
	}
	
	public BinaryTree(Object o){
		this.root = new TreePosition();
		this.root.leftChild = null;
		this.root.rightChild = null;
		this.root.element = o;
		this.root.parent = null;
		this.n = 1;
	}
	
	public void insertLeft(TreePosition p, Object o){
		if (p.leftChild==null){
			TreePosition v = new TreePosition();
			v.element = o;
			v.parent = p;
			v.leftChild = null;
			v.rightChild = null;
		    p.leftChild = v;
		    this.n++;
		}else throw new IllegalArgumentException();
	}
	
	public void insertRight(TreePosition p, Object o){
		if (p.rightChild==null){
			TreePosition v = new TreePosition();
			v.element = o;
			v.parent = p;
			v.leftChild = null;
			v.rightChild = null;
			p.rightChild = v;
			this.n++;
		}else throw new IllegalArgumentException();
	}		

	public int size(){
		return this.n;
	}
	
	public boolean isEmpty(){
		return (this.root==null);
	}
	
	public boolean isInternal(TreePosition v){
		return (v.leftChild!=null || v.rightChild!=null);
	}
	
	public boolean isExternal(TreePosition v){
		return !isInternal(v);
	}
		
	public boolean isRoot(TreePosition v){
		return (this.root==v);
	}
	
	public TreePosition parent(TreePosition v){
		if (v!=this.root) return v.parent;
		else throw new NoSuchElementException();
	}
	
	public boolean hasleftChild(TreePosition v){
		return (v.leftChild!=null);
	}
	
	public boolean hasrightChild(TreePosition v){
		return (v.rightChild!=null);
	}
	
	public boolean hasSibling(TreePosition v){
		if (v==this.root) return false;
		else return (v.parent.leftChild!=null && v.parent.rightChild!=null);
	}
	
	public TreePosition leftChild(TreePosition v){
		if (v.leftChild!=null) return v.leftChild;
		else throw new NoSuchElementException();
	}
	
	public TreePosition rightChild(TreePosition v){
		if (v.rightChild!=null) return v.rightChild;
		else throw new NoSuchElementException();
	}
	
	public TreePosition sibling(TreePosition v){
		if (hasSibling(v)){
			if (v.parent.leftChild==v) return v.parent.rightChild;
			else return v.parent.leftChild;
		}else throw new NoSuchElementException();
	}
	
	public TreePosition preorderNext(TreePosition v){
		//Geben Sie den Knoten, der nach v in der Preorder-Traversierung des Baumes bearbeitet wird, zurueck
		//Ist v der letzte Knoten in der Preorder-Traversierung, dann null zurueckgeben
		return null;
	}
	
	public TreePosition inorderNext(TreePosition v){
		//Geben Sie den Knoten, der nach v in der Inorder-Traversierung des Baumes bearbeitet wird, zurueck
		//Ist v der letzte Knoten in der Inorder-Traversierung, dann null zurueckgeben
		return null;		
	}
	
	public TreePosition postorderNext(TreePosition v){
		//Geben Sie den Knoten, der nach v in der Postorder-Traversierung des Baumes bearbeitet wird, zurueck
		//Ist v der letzte Knoten in der Postorder-Traversierung, dann null zurueckgeben
		return null;		
	}
}