import java.lang.reflect.Array;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4,5, 6, 7};
        Arrays.sort(array);
    BST tree = BST.createBSTFromArray(array);
    tree.inorder();
    }

}

class BST {
    static 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);
    }
     public static BST createBSTFromArray(int[] array) {
        BST newTree = new BST();
        if(array.length > 0) {
            newTree.root = createBSTFromArrayRecursive(array, 0, array.length - 1);
        }
        return newTree;
    }
    public static Node createBSTFromArrayRecursive(int[] array, int L, int R) {
        if(L > R) {
            return null;
        }
        int middle = (L + R) / 2;
        Node root = new Node(array[middle]);
        root.left = createBSTFromArrayRecursive(array, L, middle - 1);
        root.right = createBSTFromArrayRecursive(array, middle + 1, R);

        return root;
    }
}