/**
 * @author Ahmad Ouerfelli
 */
public class BinaryTree {

    private Node root;

    public void add(BinaryTree tree) {
        add(tree.root);
    }

    // IN traversal
    private void add(Node br) {
        add(br.left);
        add(br.n);
        add(br.right);
    }

    public void add(int n, int... nums) {
        add(n);
        for (int num : nums) {
            add(num);
        }
    }

    private void add(int n) {
        if (root == null) {
            root = new Node(n);
        } else {
            add(n, root);
        }
    }

    private void add(int n, Node br) {
        if (n > br.n) {
            if (br.right == null) {
                br.right = new Node(n);
            } else {
                add(n, br.right);
            }
        } else if (n < br.n) {
            if (br.left == null) {
                br.left = new Node(n);
            } else {
                add(n, br.left);
            }
        }
    }

    // Private because you can't access Node class outside
    private Node find(int n) {
        return find(n, root);
    }

    private Node find(int n, Node br) {
        return br == null || br.n == n ? br : find(n, n > br.n ? br.right : br.left);
    }

    public int depth(int n) {
        return depth(n, root, 1);
    }

    private int depth(int n, Node br, int height) {
        if (br == null) {
            return -1;
        }
        if (br.n == n) {
            return height;
        }
        return depth(n, br.n < n ? br.left : br.right, height + 1);
    }

    public int countLeaves() {
        return countLeaves(root);
    }

    private int countLeaves(Node br) {
        if (br == null) {
            return 0;
        }
        if (br.left == null && br.right == null) {
            return 1;
        }
        return countLeaves(br.left) + countLeaves(br.right);
    }

    public int height() {
        return maxHeight(root);
    }

    private int maxHeight(Node br) {
        return br == null ? 0 : Math.max(maxHeight(br.left), maxHeight(br.right)) + 1;
    }

    private int minHeight(Node br) {
        return br == null ? 0 : Math.min(minHeight(br.left), minHeight(br.right)) + 1;
    }

    public void delete(int n) {
        root = delete(n, root);
    }

    private Node delete(int n, Node br) {
        if (br != null) {
            if (n < br.n) {
                br.left = delete(n, br.left);
            } else if (n > br.n) {
                br.right = delete(n, br.right);
            } else {
                br = delete(br);
            }
        }
        return br;
    }

    private Node delete(Node br) {
        if (br.left == null) {
            br = br.right;
        } else if (br.right == null) {
            br = br.left;
        } else {
            // I opted to use the min-val of right subtree instead of max-val of left subtree, but I don't think it
            // really matters in any case.
            br.n = findMin(br.right);
            br.right = delete(br.n, br.right);
        }
        return br;
    }

    private int findMin(Node br) {
        while (br.left != null) {
            br = br.left;
        }
        return br.n;
    }

    public boolean isAncestor(int ancestor, int descendant) {
        return ancestor != descendant && find(descendant, find(ancestor, root)) != null;
    }

    public boolean isBalanced() {
        // TODO: What happens if negative?
        return maxHeight(root) - minHeight(root) <= 1;
    }

    public void display(Traverse order) {
        System.out.println(stringify(order));
    }

    private String stringify(Traverse order) {
        String str = stringify(order, root);
        // Remove dangling comma
        return str.substring(0, str.lastIndexOf(','));
    }

    private String stringify(Traverse order, Node br) {
        if (br == null) {
            return "";
        }
        switch (order) {
            case IN: {
                return stringify(order, br.left) + br + ", " + stringify(order, br.right);
            }
            case PRE: {
                return br + ", " + stringify(order, br.left) + stringify(order, br.right);
            }
            case POST: {
                return stringify(order, br.left) + stringify(order, br.right) + br + ", ";
            }
            default: {
                throw new IllegalArgumentException("Invalid traverse order");
            }
        }
    }

    @Override
    public String toString() {
        return stringify(Traverse.IN);
    }

    public BinaryTree() {
    }

    public enum Traverse {
        IN, PRE, POST
    }

    private static class Node {

        private int n;
        private Node left;
        private Node right;

        @Override
        public String toString() {
            return String.valueOf(n);
        }

        public Node(int n) {
            this.n = n;
        }
    }
}

/**
 * @author Ahmad Ouerfelli
 */
class BinaryTreeTest {
    public static void main(String... args) {
        BinaryTree tree = new BinaryTree();
        tree.add(1, 2, 3, 4, 5);
        tree.display(BinaryTree.Traverse.PRE);
        tree.display(BinaryTree.Traverse.IN);
        tree.display(BinaryTree.Traverse.POST);
    }
}