import java.util.*;

class BinaryTree<T extends Comparable<? super T>> {
    
    class Node<T>{
        
        Node<T> left;
        Node<T> right;
        T key;
        
        Node(T newKey) {
            left = null;
            right = null;
            key = newKey;
        }
    }
    
    private Node<T> root;
    public BinaryTree() {
        root = null;
    }
    
    public void insert(T newKey) {
        Node<T> workNode = root;
        Node<T> parentNode = null;
        while (workNode != null) {
            parentNode = workNode;
            if (newKey.compareTo(workNode.key) < 0) {
                workNode = workNode.left;
            } else {
                workNode = workNode.right;
            }
        }
        if (parentNode == null) {
            root = new Node<T>(newKey);
        } else if (newKey.compareTo(parentNode.key) < 0) {
            parentNode.left = new Node<T>(newKey);
        } else {
            parentNode.right = new Node<T>(newKey);
        }
    }
    
    public Node<T> delete(T key) {
        if (root == null) {
            return null;
        }
        
        Node<T> workNode = root;
        Node<T> parentNode = null;
        while (key.compareTo(workNode.key) != 0) {
            if (key.compareTo(workNode.key) < 0) {
                if (workNode.left == null) {
                    return null;
                }
                parentNode = workNode;
                workNode = workNode.left;
            } else {
                if (workNode.right == null) {
                    return null;
                }
                parentNode = workNode;
                workNode = workNode.right;
            }
        }
        
        if (workNode.right == null) {
            setChild(parentNode, workNode.left, workNode.key);
            return workNode;
        } else if (workNode.left == null) {
            setChild(parentNode, workNode.right, workNode.key);
            return workNode;
            
        } else {
            Node<T> replaceNode = workNode.left;
            Node<T> parentReplaceNode = workNode;
            
            while (replaceNode.right != null) {
                parentReplaceNode = replaceNode;
                replaceNode = replaceNode.right;
            }
            
            if (parentReplaceNode == workNode) {
                setChild(parentNode, replaceNode, workNode.key);
                parentReplaceNode.left = null;
                replaceNode.right = workNode.right;
                return workNode;
            } else {
                setChild(parentNode, replaceNode, workNode.key);
                parentReplaceNode.right = replaceNode.left;
                replaceNode.left = workNode.left;
                replaceNode.right = workNode.right;
                return workNode;
            }
        }
    }
    
    private Node<T> setChild
	(Node<T> targetNode, Node<T> newNode, T key) {
        if (targetNode == null) {
            root = newNode;
            return null;
        } else if (key.compareTo(targetNode.key) < 0) {
            targetNode.left = newNode;
            return targetNode;
        } else {
            targetNode.right = newNode;
            return targetNode;
        }
    }
    
    public void printTree() {
        if (root == null) {
            System.out.println("null");
        } else {
            traverseInorder(root);
            System.out.println();
        }
    }
    
    private void traverseInorder(Node<T> tempNode) {
        if (tempNode != null) {
            traverseInorder(tempNode.left);
            System.out.print("(" + tempNode.key + ") ");
            traverseInorder(tempNode.right);
        } else {
            return;
        }
    }
    
    public static void main(String[] args) {
        final int MAXKEY = 100;
        BinaryTree<Integer> tree = new BinaryTree<>();
        Random rand = new Random();
        int numberOfNodes = rand.nextInt(10);
        for (int i = 0; i < numberOfNodes; i++) {
            tree.insert(rand.nextInt(MAXKEY));
        }
        tree.printTree();
        
        for (int i = 0; i < numberOfNodes; ++i) {
            int input = 0;
            do {
                input = rand.nextInt(MAXKEY);
            } while (tree.delete(input) == null);
            System.out.println("(" + input + ") を削除");
            tree.printTree();
        }
    }
}