BST

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class BST  <Key extends Comparable<Key>>{

    private class Node{
        Key info;
        Node left,right;
        public Node(Key info, BST<Key>.Node left, BST<Key>.Node right) {
            this.info = info;
            this.left = left;
            this.right = right;
        }

    }


    Node root;


    public BST(BST<Key>.Node root) {
        super();
        this.root = root;
    }

    private Node insert(Node x, Key k)
    {
        if (x==null)
        {
            x =new Node(k,null,null);
        }
        else //drvo nije prazno
        {
        //  if (k.compareTo(x.info)==0) return null;
            if(k.compareTo(x.info)<0)
            {
                //idi lijevo
                x.left=insert(x.left,k);
            }
            else
            {
                //idi desno
                x.right=insert(x.right,k);
            }
        }
        return x;
    }

    public void insert(Key k)
    {
        root=insert(root,k);
    }

    private Node delete (Node x,Key k)
    {
        if (x==null) return x;
        int cmp=k.compareTo(x.info);
        if(cmp<0) x.left=delete(x.left,k);
        else if(cmp>0) x.right=delete(x.right,k);
        else
        {
            if(x.left==null)
                x=x.right;
            else if(x.right==null) x=x.left;
            else
            {
                Node t=x.right;
                while(t.left!=null) t=t.left;
                x.info=t.info;
                x.right=delete(x.right,t.info);
            }
        }
        return x;
    }

    public void delete(Key k)
    {
        root=delete(root,k);
    }



    private void inorder (Node x)
    {
        if(x==null)
            return;
        inorder(x.left);
        System.out.println(x.info);
        inorder(x.right);
    }

    public void inorder()
    {
        inorder(root);
    }

    private int broj (Node x)
    {
        if(x==null) return 0;
        return 1+broj(x.left)+broj(x.right);
    }

    public int size()
    {
        return broj(root);
    }

    private Node getElR(Node n, Key x)
    {
        if(n==null) return null;
        if(x==null) throw new IllegalArgumentException("argument u metodu getEl je null :(");
        int cmp=x.compareTo(n.info);
        if (cmp==0) return n;
        if(cmp<0) return getElR(n.left,x);
        return getElR(n.right,x);
    }
    public Node getR(Key k)
    {
        return getElR(root,k);
    }



    private Node getElN(Node n, Key x)
    {
        if(n==null) return null;
        if(x==null) throw new IllegalArgumentException("argument u metodu getEl je null :(");
        int cmp=0;
        Node curr =n;
        while (curr != null)
        {
            cmp=x.compareTo(curr.info);
            if (cmp==0) return curr;
            if(cmp<0) curr=curr.left;
            else curr=curr.right;
        }
        return null;
    }
    public Node getN(Key k)
    {
        return getElN(root,k);
    }


    public boolean contains(Key k)
    {
        return getR(k)!=null;
    }

    //dubina stabla











    public ArrayList<Integer> djelioci(int n)
    {
        /*  ArrayList<Integer> res= new ArrayList<>();
        //rjesenje slozenosti O(n)
        res.add(1);
        for (int i=2;i<=n/2;i++)
        {
            if (n%i==0)
            {
                res.add(i);
            }

        }
        if(n>1)res.add(n);

        return res;
    */

        ArrayList<Integer> res= new ArrayList<>();
        //rjesenje slozenosti O(sqrt(n))
        int i;
        for (i=1;i*i<n;i++)
        {
            if (n%i==0)
            {
                res.add(i);
                res.add(n/i);
            }
        }
        if(i*i==n)res.add(i);
        return res;

    }

    ArrayList<Integer> sito(int n)
    {
        return null;

    }


    public void printLevel()
    {
        Node n= root;
        Queue<Node> red = new LinkedList<>();
        red.offer(n);
        while(!red.isEmpty())
        {
            n=red.poll();
            System.out.println(n.info);
            if(n.left!=null) red.offer(n.left);
            if(n.right!=null) red.offer(n.right);
        }
    }

    public void inorderNRec()
    {
        Node t= root;
        Deque<Node> stek=new ArrayDeque<>();
        while (t!=null)
        {
            stek.addFirst(t);
            t=t.left;
        }
        while(!stek.isEmpty())
        {
            t=stek.removeFirst();
            System.out.println(t.info);
            t=t.right;
            while (t!=null)
            {
                stek.addFirst(t);
                t=t.left;
            }
        }

    }

// Tree, Hash, LinkedHash +(Set || Map)

    public void duplikati(String filename)
    {
        Set<String> jed = new HashSet<>();
        Set<String> dup = new TreeSet<>();
        BufferedReader br;
        String line="";
        String [] rijeci;
        try {
            br = new BufferedReader(new FileReader(new File(filename)));
            while ((line= br.readLine())!=null)
            {
                rijeci=line.split("\\b");
                for(String s:rijeci)
                {
                    boolean b=jed.add(s);
                    if (!b)
                    {
                        dup.add(s);
                    }
                }

            }
            jed.removeAll(dup);
            System.out.println("jed: "+jed.size()+" "+jed);
            System.out.println("dup: "+dup.size()+" "+dup);
            Iterator <String> it;
            for( it=jed.iterator(); it.hasNext();)
            {
                if(it.next().length()<2) it.remove();
            }
            System.out.println("jed: "+jed.size()+" "+jed);

        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

    }










}