package trees;

class Node {
    private Object item;
    private Node left;
    private Node right;

    public Node(Object item) {
        this(item, null, null);
    }

    public Node(Object item, Node left, Node right) {
        this.item = item;
        this.left = left;
        this.right = right;
    }

    private void visit() {
        System.out.print(item + " ");
    }

    public void preorder() {
        visit();
        if (left != null)
            left.preorder();
        if (right != null)
            right.preorder();
    }

    public void postorder() {
        if (left != null)
            left.postorder();
        if (right != null)
            right.postorder();
        visit();
    }

    public void inorder() {
        if (left != null)
            left.inorder();
        visit();
        if (right != null)
            right.inorder();
    }

    public int size() {
        int size = 1;
        if (left != null)
            size += left.size();
        if (right != null)
            size += right.size();
        return size;
    }

    public int height() {
        int height = -1;
        if (left != null)
            if (left.height() > height)
                height = left.height();
        if (right != null)
            if (right.height() > height)
                height = right.height();
        return height + 1;
    }

    public Node duplicate() {
        Node n = new Node(item);
        if (left != null)
            n.left = left.duplicate();
        if (right != null)
            n.right = right.duplicate();
        return n;
    }

}

class BinaryTree {
    public static Node makeTree() {
        return new Node("*", new Node("+", new Node("*", new Node("2"),
                new Node("4")), new Node("/", new Node("8"), new Node("4"))),
                new Node("-", new Node("2"), new Node("4")));
    }

    public static void main(String[] args) {
        Node tree = makeTree();
        System.out.println("PREorder");
        tree.preorder();
        System.out.println();
        System.out.println("POSTorder");
        tree.postorder();
        System.out.println();
        System.out.println("INorder");
        tree.inorder();
        System.out.println();
        System.out.println("size " + tree.size());
        System.out.println("height " + tree.height());
        Node tree2 = tree.duplicate();
        System.out.println("INorder");
        tree2.inorder();
        System.out.println();
    }
}