public class SimpleTree {
    private class Node {
        private int key;
        private String data;
        private Node right;
        private Node left;
        
        private Node(int k, String d) {
            key = k;
            data = d;
            // left and right will be null
        }
    }
  
    private Node root;
    
    public SimpleTree() {
        root = null;
    }

    public void init() {
        root = new Node(26, "N.America");
        root.left = new Node(22, "Qatar");
        root.right = new Node(82, "Spain");
        root.left.left = new Node(14, "Brazil");
        root.right.left = new Node(70, "Mexico");
        root.right.right = new Node(90, "Italy");
        root.right.left.left = new Node(66, "England");
    }

    public String delete(int key) {
        Node parent = null;
        Node trav = root;
        while (trav != null && trav.key != key) {
            parent = trav;
            if (key < trav.key) {
                trav = trav.left;
            } else {
                trav = trav.right;
            }
        }

        if (trav == null) {
            return null;
        } else {
            String removedData = trav.data;
            deleteNode(trav, parent);
            return removedData;
        }
    }
    
    private void deleteNode(Node toDelete, Node parent) {
        if (toDelete.left != null && toDelete.right != null) {
            Node replaceParent = toDelete;
            Node replace = toDelete.right;
            while (replace.left != null) {
                replaceParent = replace;
                replace = replace.left;
            }

            toDelete.key = replace.key;
            toDelete.data = replace.data;

            deleteNode(replace, replaceParent);
        } else {
            Node toDeleteChild;
            if (toDelete.left != null) {
                toDeleteChild = toDelete.left;
            } else {
                toDeleteChild = toDelete.right;
            }

            if (toDelete == root) {
                root = toDeleteChild;
            } else if (toDelete.key < parent.key) {
                parent.left = toDeleteChild;
            } else {
                parent.right = toDeleteChild;
            }
        }
    }
    
    public static void main(String[] args) {
        SimpleTree tree = new SimpleTree();
        tree.init();
        
        System.out.println(tree.delete(22));
        System.out.println(tree.delete(26));
        System.out.println(tree.delete(14));
    }
}