import java.util.*;

public class LinkedBinaryTree implements BinaryTree {
    private Node root;
    private int size;

    public LinkedBinaryTree() {
        root = null;
        size = 0;
    }
    public LinkedBinaryTree(Object element) {
        root = new Node(element, null, null, null);
        size = 1;
    }
    public LinkedBinaryTree(Object element, BinaryTree leftTree, BinaryTree rightTree) throws BinaryTreeException {
        Node leftNode = (Node) leftTree.root();
        Node rightNode = (Node) rightTree.root();
        root = new Node(element, null, leftNode, rightNode);
        leftNode.parent = root;
        rightNode.parent = root;
        size = leftTree.size() + rightTree.size() + 1;
    }
    
    private Node checkPosition(Position position) throws BinaryTreeException {
        try {
            return ((Node) position);
        } catch (ClassCastException e) {
            throw new BinaryTreeException("Invalid position.");
        }
    }

    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return (size == 0);
    }
    public Position root() throws BinaryTreeException {
        if (isEmpty()) {
            throw new BinaryTreeException("Empty tree has no root.");
        }
        return root;
    }
    public Position parent(Position position) throws BinaryTreeException {
        if (isRoot(position)) {
            throw new BinaryTreeException("Invalid position.");
        }
        Node node = checkPosition(position);
        return node.parent;
    }
    public Position leftChild(Position position) throws BinaryTreeException {
        if (isExternal(position)) {
            throw new BinaryTreeException("Invalid position.");
        }
        Node node = checkPosition(position);
        return node.left;
    }
    public Position rightChild(Position position) throws BinaryTreeException {
        if (isExternal(position)) {
            throw new BinaryTreeException("Invalid position.");
        }
        Node node = checkPosition(position);
        return node.right;
    }
    public boolean isInternal(Position position) throws BinaryTreeException {
        Node node = checkPosition(position);
        return (node.left != null || node.right != null);
    }
    public boolean isExternal(Position position) throws BinaryTreeException {
        return (!isInternal(position));
    }
    public boolean isRoot(Position position) throws BinaryTreeException {
        Node node = checkPosition(position);
        return (node == root);
    }
}