public class LinkedBinaryTree<T> extends BinaryTree<T> {
	private class Node implements TreeCursor<T> {
		public T element;
		public Node leftSon;
		public Node rightSon;
		
		public Node(Node left, T item, Node right) {
			this.element = item;
			this.leftSon = left;
			this.rightSon = right;
		}
		
		public Node(T element) {
			this(null, element, null);
		}		
	}
	
	private Node root_;
	private int size_;
	
	public LinkedBinaryTree(LinkedBinaryTree<T> left, T element, LinkedBinaryTree<T> right) {
		this.root_ = new Node(left.root_, element, right.root_);
		this.size_ = left.size() + right.size() + 1;
		left.root_ = null;
		left.size_ = 0;
		right.root_ = null;
		right.size_ = 0;
	}
	
	public LinkedBinaryTree(T element) {
		this.root_ = new Node(element);
		this.size_ = 1;
	}

	public LinkedBinaryTree() {
		this.root_ = null;
		this.size_ = 0;
	}
	
	@Override
	public int size() {
		return this.size_;
	}
	
	public T rootElement() {
		return this.root_.element;
	}

	public BinaryTree<T> leftSon() {
		LinkedBinaryTree<T> son = new LinkedBinaryTree<T>();
		if ( (this.root_ != null) && (this.root_.leftSon != null) ) {
			son.root_ = this.root_.leftSon;
			this.root_.leftSon = null;
		}
		return son;
	}

	public BinaryTree<T> rightSon() {
		LinkedBinaryTree<T> son = new LinkedBinaryTree<T>();
		if ( (this.root_ != null) && (this.root_.rightSon != null) ) {
			son.root_ = this.root_.rightSon;
			this.root_.rightSon = null;
		}
		return son;
	}

	@Override
	public boolean isEmpty() {
		return this.root_ == null;
	}

	@Override
	public TreeCursor<T> root() {
		return this.root_;
	}

	@Override
	public TreeCursor<T> toLeft(TreeCursor<T> c) {
		return ((Node)c).leftSon;
	}

	@Override
	public TreeCursor<T> toRight(TreeCursor<T> c) {
		return ((Node)c).rightSon;
	}

	@Override
	public T getElement(TreeCursor<T> c) {
		return ((Node)c).element;
	}
}