import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;



class TreeNode
{
    private int data;
   private TreeNode left;
    private TreeNode right;
     boolean isEmpty;

    public TreeNode getRight() {
        return right;
    }

    public TreeNode getLeft() {
        return left;
    }

    public int getData() {
        return data;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setData(int data) {
        this.data = data;
        this.isEmpty = false;
    }
    public TreeNode()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
        isEmpty = true;
    }

    @Override
    public String toString() {
        return "Значение данных этой ноды равно: " + data;
    }
}

public class TreeContainer {
    private TreeNode head;
    private int count;

    public TreeContainer(){
        this.head = null;
        this.count = 0;
    }

    public void setCount(int count) {
        this.count = count;
    }

    public void setHead(TreeNode head) {
        this.head = head;
    }

    public int getCount() {
        return count;
    }

    public TreeNode getHead() {
        return head;
    }
    public void countIncr()
    {
        this.count++;
    }

    public boolean bin_search(TreeContainer searchTree, int item)
    {
        TreeNode searchNode = new TreeNode();
        searchNode = searchTree.getHead();
        for(;;)
        {
            if(searchNode == null) return false;
            else if(item == searchNode.getData()) return true;
            else if(item > searchNode.getData()) searchNode = searchNode.getRight();
            else searchNode = searchNode.getLeft();
        }
    }

    public static void insert(TreeContainer searchTree, int item)
    {
        TreeNode searchNode = searchTree.getHead();
        TreeNode tempNode = searchTree.getHead();
        if(searchNode == null)
        {
            TreeNode temp = new TreeNode();
            temp.setData(item);
            temp.setLeft(null);
            temp.setRight(null);
            searchTree.setHead(temp);
            return;
        }
        while(true)
        {
            if(searchNode.isEmpty)
            {
                    searchNode.setData(item);
                    searchNode.setLeft(null);
                    searchNode.setRight(null);
                    searchTree.countIncr();
                    return;
            }

            else if(item == searchNode.getData())
                return;
            else if(item > searchNode.getData())
            {
                tempNode = searchNode;
                searchNode = searchNode.getRight();
                if(searchNode == null)
                    searchNode = new TreeNode();
                tempNode.setRight(searchNode);
            }
            else if(item < searchNode.getData())
            {
                tempNode = searchNode;
                searchNode = searchNode.getLeft();
                if(searchNode == null)
                    searchNode = new TreeNode();
                tempNode.setLeft(searchNode);
            }
        }

    }

    public TreeNode searchForElem(TreeNode head, int item)
    {
        TreeNode finalAnswer = new TreeNode();
        if(head == null) return null;
        else if(item == head.getData()) {
            System.out.println("Я на самом деле жив");
            return head;
        }
        else if(item > head.getData())
        {
            finalAnswer = searchForElem(head.getRight(),item);
        }
        else if(item < head.getData());
            finalAnswer = searchForElem(head.getLeft(),item);
        System.out.println("Какого-то хуя меня вызвали");
        return finalAnswer;
    }

     public void delete(int item)
    {
        boolean isFound = false;
        TreeNode temp = head;
        TreeNode father = new TreeNode();
        while(!isFound)
        {
            if(temp == null) return;
            else if(temp.getData() == item)
            {
                isFound = true;
            }
            else if(temp.getData() > item)
            {
                father = temp;
                temp = temp.getLeft();
            }
            else if(temp.getData() < item)
            {
                father = temp;
                temp = temp.getRight();
            }
        }
        temp.setData(-7547);
        count--;
        return;
    }

    static public void walk(TreeNode searchNode)
    {
        if(searchNode == null){
            return;
        }
        walk(searchNode.getLeft());
        if(searchNode.getData() != -7547)
            System.out.println(searchNode.getData());
        walk(searchNode.getRight());
    }

    static void walk2(TreeContainer myTree)
    {
        walk(myTree.getHead());
    }

    static void destroy(TreeNode searchNode)
    {
        if(searchNode == null) return;
        destroy(searchNode.getLeft());
        destroy(searchNode.getRight());
    }
    void destroy(TreeContainer searchTree)
    {
        destroy(searchTree.getHead());
    }

    public static TreeNode treeMinimum(TreeContainer searchTree)
    {
        TreeNode  searchNode = searchTree.getHead();
        while(searchNode.getLeft() != null)
            searchNode = searchNode.getLeft();
        return searchNode;
    }

    public static TreeNode treeMaximum (TreeContainer searchTree)
    {
        TreeNode searchNode;
        searchNode = searchTree.getHead();
        while(searchNode.getRight() != null)
            searchNode = searchNode.getRight();
        return searchNode;
    }

    boolean isBST(TreeContainer searchTree)
    {
        return(isBSTUtil(searchTree.getHead(),treeMinimum(searchTree).getData(),treeMaximum(searchTree).getData()));
}
    public boolean isBSTUtil(TreeNode node, int min,int max)
    {
        if(node == null) return true;
        if(node.getData()<min || node.getData()>max) return false;
        return(isBSTUtil(node.getLeft(),min,node.getData()) && isBSTUtil(node.getRight(),node.getData()+1,max));
    }

    public static void main(String[] args) throws IOException {
        TreeContainer tc = new TreeContainer();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Введите 10 элементов в дерево");

        for(int i = 0;i<10;i++) {
            insert(tc, Integer.parseInt(reader.readLine()));
        }
        walk2(tc);
        System.out.println("Выберите элемент, который хотите удалить");
        tc.delete(Integer.parseInt(reader.readLine()));
        walk2(tc);

    }
}