public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(45);
        tree.insert(10);
        tree.insert(7);
        tree.insert(12);
        tree.insert(90);
        tree.insert(50);

        tree.inorder();
        System.out.println();
        tree.delete(10);

        tree.inorder();
    }

}

class BST {
    class Node {
        int info;
        Node left, right;

        Node(int info) {
            this.info = info;
            left = null;
            right = null;
        }
    }
    Node root;
    BST() {
        root = null;
    }
    void insert(int value) {
        root = insertRecursive(root, value);
    }
    Node insertRecursive(Node node, int value) {
        if(node == null) {
            node = new Node(value);
            return node;
        }
        if(value < node.info) {
            node.left = insertRecursive(node.left, value);
        }
        else if(value > node.info) {
            node.right = insertRecursive(node.right, value);
        }
        return node;
    }
    void delete(int value) {
        root = deleteRecursive(root, value);
    }
    Node deleteRecursive(Node node, int value) {
        if(node == null) {
            return null;
        }

        if(value < node.info) {
            node.left = deleteRecursive(node.left, value);
        }
        else if(value > node.info) {
            node.right = deleteRecursive(node.right, value);
        }
        else if(value == node.info){ // sme go nasle, treba da go izbriseme
            if(node.left == null) {
                return node.right;
            }
            else if(node.right == null) {
                return node.left;
            }
            node.info = findMinimumValue(node.right);
            node.right = deleteRecursive(node.right, node.info);
        }
        return node;
    }
    int findMinimumValue(Node node) {
        int result = node.info;
        while(node.left != null) {
            result = node.left.info;
            node = node.left;
        }
        return result;
    }
    void inorder() {
        inorderRecursive(root);
    }
    void inorderRecursive(Node node) {
        if(node == null) {
            return;
        }
        inorderRecursive(node.left);
        System.out.println(node.info + " ");
        inorderRecursive(node.right);
    }
}