[ADSx] - Binary Tree Fun

import java.util.*;

/**
 * https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java
 * */

public class BinaryTreeFun {

    public static void inOrder(Node node) {
        if (node == null) return;
        /* L O R */
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public static void preOrder(Node node) {
        if (node == null) return;
        /* O L R */
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void postOrder(Node node) {
        if (node == null) return;
        /* L R O*/
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public static void zigzagOrder(Node node, int height, boolean side) {
        if (node == null) return;

        if (height == 1) {
            System.out.print(node.data + " ");
            return;
        }

        if (side) {
            zigzagOrder(node.left, height - 1, side);
            zigzagOrder(node.right, height - 1, side);
        } else {
            zigzagOrder(node.right, height - 1, side);
            zigzagOrder(node.left, height - 1, side);
        }
    }

    public static void printZigZag(Node node) {
        if (node == null) return;
        int height = height(node);
        boolean side = false;
        System.out.println("Height: " + height);
        for (int i = 1; i <= height; i++) {
            System.out.printf("Level (%d): ", i);
            zigzagOrder(node, i, side);
            System.out.println();
            side = !side;
        }
    }

    public static void printZigZagStack(Node node) {
        /**
         * Works, but prints as it reads, not as we read the tree in zigzag
         * */

        if (node == null) return;
        StringBuffer sb = new StringBuffer();

        Stack<Node> currentLevel = new Stack<>();
        Stack<Node> nextLevel = new Stack<>();

        currentLevel.push(node);

        boolean leftToRight = true;
        while (!currentLevel.isEmpty()) {
            Node current = currentLevel.pop();

            if (current != null) {
                sb.append(current.data).append(" ");
                if (leftToRight) {
                    if (current.right != null) nextLevel.push(current.right);
                    if (current.left != null) nextLevel.push(current.left);
                } else {
                    if (current.right != null) nextLevel.push(current.right);
                    if (current.left != null) nextLevel.push(current.left);
                }
            }

            //System.out.printf("C: %-40s N: %-40s\n", currentLevel, nextLevel);
            if (currentLevel.isEmpty()) {
                leftToRight = !leftToRight;

                while (!nextLevel.isEmpty()) {
                    Node pop = nextLevel.pop();
                    currentLevel.push(pop);
                }
            }
        }
        System.out.println(sb.toString());
    }

    public static void zigzagStack(Node node) {
        if (node == null) return;
        StringBuffer sb = new StringBuffer();

        Stack<Node> currentLevel = new Stack<>();
        Stack<Node> nextLevel = new Stack<>();

        int height = height(node);

        currentLevel.push(node);

        for (int i = 0; i < height; i++) {
            sb.append("\n");
            if (i % 2 == 0) {

                while (!currentLevel.isEmpty()) {
                    Node current = currentLevel.pop();
                    sb.append(current.data).append(" ");
                    if (current.right != null) nextLevel.push(current.right);
                    if (current.left != null) nextLevel.push(current.left);
                }
            } else {
                while (!nextLevel.isEmpty()) {
                    Node current = nextLevel.pop();
                    sb.append(current.data).append(" ");
                    if (current.left != null) currentLevel.push(current.left);
                    if (current.right != null) currentLevel.push(current.right);
                }
            }
        }
        System.out.println(sb.toString() + System.lineSeparator());
    }

    public static int height(Node node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public static int heightQueue(Node node) {
        Queue<Node> queue = new LinkedList<>(); // ArrayDeque doesn't allow null values
        int height = 0;
        queue.add(node);
        queue.add(null); // Null serves as a marker
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll == null) {
                if (!queue.isEmpty()) {
                    queue.add(null);
                }
                height++;
            } else {
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
            }
        }
        return height;
    }

    public static void printNodesAtHeight(Node node, int height) {
        if (node == null) return;

        if (height == 1) System.out.print(" " + node.data);
        else {
            printNodesAtHeight(node.left, height - 1);
            printNodesAtHeight(node.right, height - 1);
        }
    }

    public static void levelOrder(Node node) {
        System.out.print(System.lineSeparator());
        int height = height(node);
        for (int i = 1; i <= height; i++) {
            printNodesAtHeight(node, i);
            System.out.print(System.lineSeparator());
        }
    }

    public static void BFS(Node node) {
        Queue<Node> queue = new ArrayDeque<>();
        if (node == null) return;
        queue.add(node);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            System.out.print(" " + poll.data);
            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);
        }

    }

    public static void inOrderStack(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();

        Node node = root;

        // Go all the way to the left
        while (node != null) {
            stack.push(node);
            node = node.left;
        }

        // Leftmost will be on top of the stack
        while (stack.size() > 0) {
            node = stack.pop();
            System.out.print(node.data + " ");
            if (node.right != null) { // Check if node has a right
                node = node.right;

                while (node != null) { // If it does got all the way to the left for that node
                    stack.push(node);
                    node = node.left;
                }
            }
        }
    }

    public static void levelOrderQueue(Node node) {
        Queue<Node> queue = new ArrayDeque<>();
        int levelNodes = 0;
        if (node == null) return;
        queue.add(node);
        while (!queue.isEmpty()) {
            levelNodes = queue.size();
            while (levelNodes > 0) {
                Node poll = queue.poll();
                System.out.print(" " + poll.data);
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                levelNodes--;
            }
            System.out.print(System.lineSeparator());
        }
    }

    public static Map<Integer, Integer> map = new TreeMap<>();

    public static void printTopView(Node node, int level) {
        if (node == null) return;

        Queue<HeightNode> queue = new ArrayDeque<>();
        queue.add(new HeightNode(node, level));

        while (!queue.isEmpty()) {
            HeightNode poll = queue.poll();
            Node pollNode = poll.node;
            int pollHeight = poll.height;

            if (map.containsKey(pollHeight)) {

            } else {
                System.out.print(pollNode.data + " ");
                map.put(pollHeight, pollNode.data);
            }

            if (pollNode.left != null) {
                queue.add(new HeightNode(pollNode.left, pollHeight - 1));
            }

            if (pollNode.right != null) {
                queue.add(new HeightNode(pollNode.right, pollHeight + 1));
            }
        }
    }

    public static void printBottomView(Node node, int level) {
        if (node == null) return;

        Queue<HeightNode> queue = new ArrayDeque<>();
        queue.add(new HeightNode(node, level));

        while (!queue.isEmpty()) {
            HeightNode poll = queue.poll();
            Node pollNode = poll.node;
            int pollHeight = poll.height;

            map.put(pollHeight, pollNode.data);

            if (pollNode.left != null) {
                queue.add(new HeightNode(pollNode.left, pollHeight - 1));
            }

            if (pollNode.right != null) {
                queue.add(new HeightNode(pollNode.right, pollHeight + 1));
            }
        }
    }

    public static void printBottomViewDisplay() { // print the bottom view.
        Set<Integer> keys = map.keySet();
        for (Integer key : keys) {
            System.out.print(map.get(key) + " ");
        }

    }

    public static void printTopView(Node root) {
        if (root == null) return;

        Set<Integer> set = new HashSet<>();
        Queue<HeightNode> queue = new ArrayDeque<>();
        queue.add(new HeightNode(root, 0));

        while (!queue.isEmpty()) {
            HeightNode poll = queue.poll();
            int pollHeight = poll.height;
            Node pollNode = poll.node;

            if (!set.contains(pollHeight)) {
                set.add(pollHeight);
                System.out.print(pollNode.data + " ");
            }

            if (pollNode.left != null) queue.add(new HeightNode(pollNode.left, pollHeight - 1));
            if (pollNode.right != null) queue.add(new HeightNode(pollNode.right, pollHeight + 1));
        }
    }

    public static void printTopViewo(Node root) {//print function
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> rightStack = new Stack<>();
        Node temp = root;
        int counter = 0;
        leftStack.push(root.data);
        while (true) {
            if (temp.left != null) {
                if (counter < 0) {
                    counter++;
                } else {
                    leftStack.push(temp.left.data);
                }
                temp = temp.left;
            } else if (temp.right != null) {
                temp = temp.right;
                counter--;
            } else {
                break;
            }
        }
        counter = 0;
        temp = root;
        while (true) {
            if (temp.right != null) {
                if (counter < 0) {
                    counter++;
                } else {
                    rightStack.push(temp.right.data);
                }
                temp = temp.right;
            } else if (temp.left != null) {
                temp = temp.left;
                counter--;
            } else {
                break;
            }

        }
        while (!leftStack.isEmpty()) {
            System.out.print(leftStack.pop() + " ");
        }
        while (!rightStack.isEmpty()) {
            System.out.print(rightStack.pop() + " ");
        }
    }

    public static void main(String args[]) {
        /*
               10
            /     \
           5       15
          /  \     / \
         2    7  12   20
         */
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);
        root.right.left = new Node(12);
        root.right.right = new Node(20);
        /*root.left.left.left = new Node(6);
        root.left.right.right = new Node(66);*/

        Node doot = new Node(1);
        doot.left = new Node(2);
        doot.right = new Node(3);
        doot.left.left = new Node(4);
        doot.left.right = new Node(5);
        doot.left.right.left = new Node(6);

        printZigZag(root);

        zigzagStack(root);

        printZigZagStack(root);

    }

    public static int sum = 0;

    public static void greaterSumTree(Node root) {
        if (root == null) return;

        greaterSumTree(root.right);
        int data = root.data;
        root.data = sum;
        sum += data;
        greaterSumTree(root.left);
    }

    public static Node findNodeByData(Node node, int data) {
        if (node == null) return null;
        if (node.data == data) return node;
        Node left = findNodeByData(node.left, data);
        return left == null ? findNodeByData(node.right, data) : left;
    }

    public static Node LeastCommonAncestor(Node current, Node one, Node two) {
        if (current == null) return null;
        if (current == one || current == two) return current;

        Node left = LeastCommonAncestor(current.left, one, two);
        Node right = LeastCommonAncestor(current.right, one, two);

        if (left != null && right != null) return current;

        return left == null ? right : left;
    }

    public static int depth(Node current, Node target) {
        if (current == null) return -1;
        if (current == target) return 0;
        int left = depth(current.left, target);
        int right = depth(current.right, target);
        if (left == -1 && right == -1) return -1;
        return left == -1 ? right + 1 : left + 1;
    }

    public static int distanceBetween(Node root, Node one, Node two) {
        if (root == null || one == null || two == null) return -1;
        Node ancestor = LeastCommonAncestor(root, one, two);
        int depth1 = depth(root, ancestor);
        int depth2 = depth(root, one);
        int depth3 = depth(root, two);
        return depth2 + depth3 - 2 * depth1;
    }

    public static int successor(Node root, int data) {
        Node target = findNodeByData(root, data);
        if (target == null) return -1;
        Node successor = null;
        Node current = root;
        while (current != null && current.data != target.data) {
            if (current.data > target.data) {
                successor = current;
                current = current.left;
            } else {
                current = current.right;
            }
        }
        if (current == null) return -1;
        if (current.right == null) return successor.data;
        current = current.right;
        while (current.left != null) {
            current = current.left;
        }
        return current.data;
    }

    public static Node parent(Node node, Node target) {
        if (node == null) return null;
        if (node.left == target || node.right == target) return node;
        Node left = parent(node.left, target);
        Node right = parent(node.right, target);
        return left == null ? right : left;
    }

    public static boolean biggerThanChildren(Node node) {
        if (node == null) return true;
        if (node.left != null && !(node.data >= node.left.data)) return false;
        if (node.right != null && !(node.data >= node.right.data)) return false;
        return biggerThanChildren(node.left) && biggerThanChildren(node.right);
    }

    public static boolean isBalanced(Node node) {
        /**
         * https://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/
         * */

        if (node == null) return true;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        if (Math.abs(leftHeight - rightHeight) < 2
                && isBalanced(node.left)
                && isBalanced(node.right)) {
            return true;
        }
        return false;
    }

    public static int diameter(Node node) {
        /**
         * https://www.geeksforgeeks.org/diameter-of-a-binary-tree/
         * */

        if (node == null) return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        int leftDiameter = diameter(node.left);
        int rightDiameter = diameter(node.right);

        return Math.max(Math.max(leftDiameter, rightDiameter), leftHeight + rightHeight + 1);
    }

    public static int heightEven(Node node, boolean isEven) {
        /**
         * https://www.geeksforgeeks.org/height-binary-tree-considering-even-level-leaves/
         * call it with isEven set to false
         * */

        if (node == null) return 0;

        if (node.left == null && node.right == null) {
            if (isEven) return 1;
            else return 0;
        }

        int leftHeight = heightEven(node.left, !isEven);
        int rightHeight = heightEven(node.right, !isEven);

        if (leftHeight == 0 && rightHeight == 0) return 0;

        return 1 + Math.max(leftHeight, rightHeight);
    }

    public static boolean isBST(Node node, int min, int max) {
        /**
         * https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
         * */

        /* an empty tree is BST */
        if (node == null) return true;

        /* false if this node violates the min/max constraints */
        if (node.data < min || node.data > max) return false;

        /* otherwise check the subtrees recursively
        tightening the min/max constraints */
        // Allow only distinct values
        return (isBST(node.left, min, node.data - 1) &&
                isBST(node.right, node.data + 1, max));
    }

    public static boolean isCompleteIterative(Node node) {
        /**
         * https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/
         * */

        if (node == null) return true;

        Queue<Node> queue = new LinkedList<>();

        //  A node is ‘Full Node’ if both left and right children are not empty (or not NULL).
        boolean leftAndRightChildAreNotEmpty = false;

        queue.add(node);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();

            if (poll.left != null) {
                if (leftAndRightChildAreNotEmpty) return false;
                queue.add(poll.left);
            } else leftAndRightChildAreNotEmpty = true;

            if (poll.right != null) {
                if (leftAndRightChildAreNotEmpty) return false;
                queue.add(poll.right);
            } else leftAndRightChildAreNotEmpty = true;
        }

        return true;
    }

    public static int countNodes(Node root) {
        if (root == null) return (0);
        return (1 + countNodes(root.left) + countNodes(root.right));
    }

    /* This function checks if the binary tree is complete or not */
    public static boolean isComplete(Node root, int index, int number_nodes) {
        /**
         * https://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-solution/
         * */

        // An empty tree is complete
        if (root == null) return true;

        // If index assigned to current node is more than
        // number of nodes in tree, then tree is not complete
        if (index >= number_nodes) return false;

        // Recur for left and right subtrees
        return (isComplete(root.left, 2 * index + 1, number_nodes)
                && isComplete(root.right, 2 * index + 2, number_nodes));

    }

    /**
     * https://www.geeksforgeeks.org/boundary-traversal-of-binary-tree/
     */

    // A simple function to print leaf nodes of a binary tree
    public static void printLeaves(Node node) {
        if (node != null) {
            printLeaves(node.left);

            // Print it if it is a leaf node
            if (node.left == null && node.right == null)
                System.out.print(node.data + " ");
            printLeaves(node.right);
        }
    }

    // A function to print all left boundry nodes, except a leaf node.
    // Print the nodes in TOP DOWN manner
    public static void printBoundaryLeft(Node node) {
        if (node != null) {
            if (node.left != null) {
                // to ensure top down order, print the node
                // before calling itself for left subtree
                System.out.print(node.data + " ");
                printBoundaryLeft(node.left);
            } else if (node.right != null) {
                System.out.print(node.data + " ");
                printBoundaryLeft(node.right);
            }

            // do nothing if it is a leaf node, this way we avoid
            // duplicates in output
        }
    }

    // A function to print all right boundry nodes, except a leaf node
    // Print the nodes in BOTTOM UP manner
    public static void printBoundaryRight(Node node) {
        if (node != null) {
            if (node.right != null) {
                // to ensure bottom up order, first call for right
                //  subtree, then print this node
                printBoundaryRight(node.right);
                System.out.print(node.data + " ");
            } else if (node.left != null) {
                printBoundaryRight(node.left);
                System.out.print(node.data + " ");
            }
            // do nothing if it is a leaf node, this way we avoid
            // duplicates in output
        }
    }

    // A function to do boundary traversal of a given binary tree
    public static void printBoundary(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");

            // Print the left boundary in top-down manner.
            printBoundaryLeft(node.left);

            // Print all leaf nodes
            printLeaves(node.left);
            printLeaves(node.right);

            // Print the right boundary in bottom-up manner
            printBoundaryRight(node.right);
        }
    }

}

class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    @Override
    public String toString() {
        return String.format("%d ", data);
    }
}

class HeightNode {
    Node node;
    int height;

    public HeightNode(Node node, int height) {
        this.node = node;
        this.height = height;
    }
}

class BTree<E> {

    /**
     * Lab 9: 2 for threaded tree
     * */
/*
    public static boolean check(BTree<Integer> tree) {

        BNode<Integer> current = tree.head.left;

        while (current.ltag == '+')
            current = current.left;

        BNode<Integer> succ = tree.successorInorder(current);

        while (succ != tree.head) {
            if ((succ.info - current.info) != 1){
                return false;
            }

            current = succ;
            succ = tree.successorInorder(current);
        }
        return true;
    }
*/

    /**
     * Lab 7: 3
     */
    public BNode<E> find(BNode<E> temp, E elem) {

        BNode<E> result = null;

        if (temp == null) return null;
        if (temp.info.equals(elem)) return temp;
        if (temp.left != null) result = find(temp.left, elem);
        if (result == null) result = find(temp.right, elem);

        return result;
    }

    public int sumLeft(BNode<? extends Number> node, BNode<? extends Number> root) {
        if (node == null) return 0;

        if (node.info.intValue() < root.info.intValue()) {
            return sumLeft(node.left, root) + sumLeft(node.right, root) + node.info.intValue();
        }
        return sumLeft(node.left, root) + sumLeft(node.right, root);
    }

    public int sumRight(BNode<? extends Number> node, BNode<? extends Number> root) {
        if (node == null) return 0;

        if (node.info.intValue() > root.info.intValue())
            return sumRight(node.left, root) + sumRight(node.right, root) + node.info.intValue();
        return sumRight(node.left, root) + sumRight(node.right, root);
    }

    /**
     * Lab 7: 2
     */
    public void PreorderNonRecursive() {
        Stack<BNode<E>> stack = new Stack<>();
        BNode<E> current = root;

        /* Root Left Right */

        while (true) {
            while (current != null) {
                System.out.print(current.info + " ");
                stack.push(current);
                current = current.left;
            }

            if (stack.isEmpty()) break;

            /* Restart */
            current = stack.pop();
            current = current.right;
        }
    }

    public BNode<E> root;

    public BTree() {
        root = null;
    }

    public BTree(E info) {
        root = new BNode<E>(info);
    }

    public void makeRoot(E elem) {
        root = new BNode<E>(elem);
    }

    public BNode<E> addChild(BNode<E> node, int where, E elem) {

        BNode<E> tmp = new BNode<E>(elem);

        if (where == BNode.LEFT) {
            if (node.left != null)  // veke postoi element
                return null;
            node.left = tmp;
        } else {
            if (node.right != null) // veke postoi element
                return null;
            node.right = tmp;
        }

        return tmp;
    }

    public void inorder() {
        System.out.print("INORDER: ");
        inorderR(root);
        System.out.println();
    }

    public void inorderR(BNode<E> n) {
        if (n != null) {
            inorderR(n.left);
            System.out.print(n.info.toString() + " ");
            inorderR(n.right);
        }
    }

    public void preorder() {
        System.out.print("PREORDER: ");
        preorderR(root);
        System.out.println();
    }

    public void preorderR(BNode<E> n) {
        if (n != null) {
            System.out.print(n.info.toString() + " ");
            preorderR(n.left);
            preorderR(n.right);
        }
    }

    public void postorder() {
        System.out.print("POSTORDER: ");
        postorderR(root);
        System.out.println();
    }

    public void postorderR(BNode<E> n) {
        if (n != null) {
            postorderR(n.left);
            postorderR(n.right);
            System.out.print(n.info.toString() + " ");
        }
    }

    public void inorderNonRecursive() {
        Stack<BNode<E>> s = new Stack<BNode<E>>();
        BNode<E> p = root;
        System.out.print("INORDER (nonrecursive): ");

        while (true) {
            // pridvizuvanje do kraj vo leva nasoka pri sto site koreni
            // na potstebla se dodavaat vo magacin za podocnezna obrabotka
            while (p != null) {
                s.push(p);
                p = p.left;
            }

            // ako magacinot e prazen znaci deka stebloto e celosno izminato
            if (s.isEmpty())
                break;

            p = s.peek();
            // pecatenje (obrabotka) na jazelot na vrvot od magacinot
            System.out.print(p.info.toString() + " ");
            // brisenje na obraboteniot jazel od magacinot
            s.pop();
            // pridvizuvanje vo desno od obraboteniot jazel i povtoruvanje na
            // postapkata za desnoto potsteblo na jazelot
            p = p.right;

        }
        System.out.println();

    }

    int insideNodesR(BNode<E> node) {
        if (node == null)
            return 0;

        if ((node.left == null) && (node.right == null))
            return 0;

        return insideNodesR(node.left) + insideNodesR(node.right) + 1;
    }

    public int insideNodes() {
        return insideNodesR(root);
    }

    int leavesR(BNode<E> node) {
        if (node != null) {
            if ((node.left == null) && (node.right == null))
                return 1;
            else
                return (leavesR(node.left) + leavesR(node.right));
        } else {
            return 0;
        }
    }

    public int leaves() {
        return leavesR(root);
    }

    int depthR(BNode<E> node) {
        if (node == null)
            return 0;
        if ((node.left == null) && (node.right == null))
            return 0;
        return (1 + Math.max(depthR(node.left), depthR(node.right)));
    }

    public int depth() {
        return depthR(root);
    }

    void mirrorR(BNode<E> node) {
        BNode<E> tmp;

        if (node == null)
            return;

        // simetricno preslikuvanje na levoto i desnoto potsteblo
        mirrorR(node.left);
        mirrorR(node.right);

        // smena na ulogite na pokazuvacite na momentalniot jazel
        tmp = node.left;
        node.left = node.right;
        node.right = tmp;

    }

    public void mirror() {
        mirrorR(root);
    }

}

class BNode<E> {

    public E info;
    public BNode<E> left;
    public BNode<E> right;

    static int LEFT = 1;
    static int RIGHT = 2;

    public BNode(E info) {
        this.info = info;
        left = null;
        right = null;
    }

    public BNode(E info, BNode<E> left, BNode<E> right) {
        this.info = info;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "BNode{" +
                "info=" + info +
                '}';
    }
}

class BinarySearchTree<E extends Comparable<E>> {

    /**
     * The tree root.
     */
    private BNode<E> root;

    /**
     * Construct the tree.
     */
    public BinarySearchTree() {
        root = null;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     *
     * @param x the item to insert.
     */
    public void insert(E x) {
        root = insert(x, root);
    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     *
     * @param x the item to remove.
     */
    public void remove(E x) {
        root = remove(x, root);
    }

    /**
     * Find the smallest item in the tree.
     *
     * @return smallest item or null if empty.
     */
    public E findMin() {
        return elementAt(findMin(root));
    }

    /**
     * Find the largest item in the tree.
     *
     * @return the largest item of null if empty.
     */
    public E findMax() {
        return elementAt(findMax(root));
    }

    /**
     * Find an item in the tree.
     *
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public BNode<E> find(E x) {
        return find(x, root);
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty() {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     *
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree() {
        if (isEmpty()) {
            System.out.println("Empty tree");
        } else {
            printTree(root);
        }
    }

    /**
     * Internal method to get element field.
     *
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private E elementAt(BNode<E> t) {
        if (t == null)
            return null;
        return t.info;
    }

    /**
     * Internal method to insert into a subtree.
     *
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BNode<E> insert(E x, BNode<E> t) {
        if (t == null) {
            t = new BNode<E>(x, null, null);
        } else if (x.compareTo(t.info) < 0) {
            t.left = insert(x, t.left);
        } else if (x.compareTo(t.info) > 0) {
            t.right = insert(x, t.right);
        } else ;  // Duplicate; do nothing
        return t;
    }

    /**
     * Internal method to remove from a subtree.
     *
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     *
     * Time Complexity O(height) = O(logn)
     */

    /**
     * Because in the worst case this algorithm must search from the root of the tree to the leaf farthest from the root,
     * the search operation takes time proportional to the tree's height. On average,
     * binary search trees with n nodes have O(log n) height. However, in the worst case,
     * binary search trees can have O(n) height, when the unbalanced tree resembles a linked list (degenerate tree).
     */
    private BNode<E> remove(Comparable x, BNode<E> t) {
        if (t == null)
            return t;   // Item not found; do nothing

        if (x.compareTo(t.info) < 0) {
            t.left = remove(x, t.left);
        } else if (x.compareTo(t.info) > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) { // Two children
            t.info = findMin(t.right).info;
            t.right = remove(t.info, t.right);
        } else {
            if (t.left != null)
                return t.left;
            else
                return t.right;
        }
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private BNode<E> findMin(BNode<E> t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    /**
     * Internal method to find the largest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private BNode<E> findMax(BNode<E> t) {
        if (t == null) {
            return null;
        } else if (t.right == null) {
            return t;
        }
        return findMax(t.right);
    }

    /**
     * Internal method to find an item in a subtree.
     *
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BNode<E> find(E x, BNode<E> t) {
        if (t == null)
            return null;

        if (x.compareTo(t.info) < 0) {
            return find(x, t.left);
        } else if (x.compareTo(t.info) > 0) {
            return find(x, t.right);
        } else {
            return t;    // Match
        }
    }

    /**
     * Internal method to print a subtree in sorted order.
     *
     * @param t the node that roots the tree.
     */
    private void printTree(BNode<E> t) {
        if (t != null) {
            printTree(t.left);
            System.out.println(t.info);
            printTree(t.right);
        }
    }

    // Test program
    public static void main(String[] args) {
        Random r = new Random(System.currentTimeMillis());
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();

        for (int i = 0; i < 10; i++) {
            bst.insert(Math.abs(i - 10));
        }


        bst.printTree();

        bst.remove(4);
        bst.printTree();

    }
}