BinarySearchTree

import java.util.Stack;

/*********************** BNode ********************/

class BNode <E extends Comparable <E>>
{
    public E info;
    public BNode <E> left;
    public BNode <E> right;

public BNode(E info) { //kreira jazol list
this.info = info;
left = null;
right = null;
}
public BNode(E info, BNode<E> left, BNode<E> right) {
this.info = info;
this.left = left;
this.right = right;
}
}

/*********************** BTree ********************/

class BSTree <E extends Comparable<E>>
{
    public BNode<E> root;
    public BSTree()
    {
        root = null;
    }
    public BSTree(E info)
    {
        root = new BNode(info);
    }

public void inorder() {
System.out.print("INORDER: ");
inorderR(root);
System.out.println();
}
public void inorderR(BNode<E> n) {
if (n != null) {
inorderR(n.left);
System.out.print(n.info.toString()+ " ");
inorderR(n.right);  }
}
public void preorder() {
System.out.print("PREORDER: ");
preorderR(root);
System.out.println();
}
public void preorderR(BNode<E> n) {
if (n != null) {
System.out.print(n.info.toString()+ " ");
preorderR(n.left);
preorderR(n.right);
}
}
public void postorder() {
System.out.print("POSTORDER: ");
postorderR(root);
System.out.println();
}
public void postorderR(BNode<E> n) {
if (n != null) {
postorderR(n.left);
postorderR(n.right);
System.out.print(n.info.toString()+ " ");
}
}
public void inorderUsingStack(BNode <E> root)
{
   Stack <BNode<E>> s =  new Stack();     // pocnuvame so prazen magacin
   BNode <E> p = root;
   System.out.print("INORDER using stack:  ");
   while(true)
     { //odime do kraj vo leva nasoka, najleviot element vo drvoto e prv element vo inorder izminuvanje
        while(p!=null)
            //vo magacinot ja smestuvame adresata na p, za da znaeme kade da se vratime otkako kje go najdeme najleviot element
            {   s.push(p);
            p = p.left;  // odi na levoto potsteblo
            }
        if (s.isEmpty()) break;   //ako sme go ispraznile magacinot togas sme go izminale celo drvo
        //se vadi i pecati informacijata sodrzana vo jazelot na vrvot od magacinot , koj e tekovno najdeniot najlev element
        //i vrvot pokazuva na sledniot jazel vo magacinot, t.e. korenot na prethodno ispechateniot element
       p = s.pop();
       System.out.print(p.info.toString()+ " ");
       /* odi na desnoto potsteblo i povtori ja postapkata ako ima levo potst*/
       p = p.right;
    }
   System.out.println();
}
public void preorderUsingStack(BNode <E> root) //zadacha od lab
{
    Stack <BNode<E>> s = new Stack();
    BNode <E> p=root;

    System.out.print("PREORDER using stack:  ");
    while(true)
    {
        while(p!=null)
        {
            if(p.right!=null)
                s.push(p.right);
            System.out.print(p.info.toString()+" ");
            p=p.left;
        }

        if (s.isEmpty()) break;
        p = s.pop();

    }

    System.out.println();

}


public boolean findR(E x, BNode <E> r)
{
        if(r==null) return false;  //ako drvoto e prazno
        int comp=x.compareTo(r.info);
        if(comp<0)  //jazolot koj go barame se naogja vo levoto poddrvo
        return  findR(x, r.left);
        else if(comp >0)  //jazolot koj go barame se naogja vo desnoto poddrvo
        return  findR(x, r.right);
        else /* (x == r.info) */
return true;
}

public boolean isEmpty()
{
    return root==null;
}

public BNode <E> findMin(BNode<E> r)
{
    if(r==null) return null; //ako drvoto e prazno
    else if(r.left==null) return r; //ova e najmaliot jazol
    else
        return findMin(r.left);
}

public BNode <E> findMax(BNode <E> r)
{
    if(r!=null)
    while(r.right!=null) r=r.right;
    return r;
}


public BNode <E> insert(E x, BNode<E> r)
{
        if (r == null) return new BNode(x); //koga kje stigneme do null pozicija, tuka treba da go dodademe jazolot
        int comp=x.compareTo(r.info);
        if (comp < 0)
        {r.left = insert(x, r.left);}  //treba da go dodavame vo levoto podsteblo
        else if (comp > 0)
        {r.right = insert(x, r.right);} //treba da go dodavame vo desnoto podsteblo
        else ; //ne pravi nishto, ne se vmetnuvaat duplikati
return r;
}

public BNode <E> insertI(E x, BNode <E> r)
{
      if (r==null)   {  return new BNode(x);  }  //ako drvoto e prazno
      BNode <E> p=r; //pochnuvame da se dvizhime od korenot, i da barame pozicija za vmetnuvanje
      int comp;
      while (p != null)
       {    comp=x.compareTo(p.info);
            if (comp<0) //barame vo levoto poddrvo
             {
                 if (p.left== null) // levo od ovoj jazel treba da se smesti noviot
              {
                   BNode <E> q = new BNode(x);
                   p.left=q;
                   break;
                  }
                 else
                     p=p.left;
            }
            else if(comp>0)
            {
                if (p.right== null) // desno od ovoj jazel treba da se smesti noviot
              {
                   BNode <E> q = new BNode(x);
                   p.right=q;
                   break;
                  }
                 else
                     p=p.right;
            }
            else break; //ne smestuvame duplikati
    }
      return r;
}

public BNode <E> remove (E x, BNode<E> r)
{
    if(r==null) return r; //ako drvoto e prazno ili ne sme go nashle jazolot
    //najprvo treba da go najdeme jazolot, pa potoa kje go brisheme
    int comp=x.compareTo(r.info);
    if(comp<0)
        r.left=remove(x,r.left);
    else if(comp>0)
        r.right=remove(x, r.right);
    else //go najdovme
    {
        if(r.left!=null && r.right!=null) //jazolot ima dve deca
            //kje go zamenime so najmaliot jazol vo levoto podsteblo
        {
            r.info=findMin(r.right).info;
            r.right=remove(r.info,r.right);
            //potoa go brishime jazolot so koj go zamenivme baraniot
        }
        else  //jazolot ima edno ili nema deca
             if(r.left!=null)
                 return r.left;
             else return r.right;
    }
    return r;
}

int numLeaves(BNode <E> r)  /* funkcija koja go vrakja brojot na listovi */
{
    if(r==null) return 0; //ako stigneme do kraj na nekoe poddrvo
    if(r.left==null && r.right==null) //list e
        return 1+numLeaves(r.left)+numLeaves(r.right);
    else
        return numLeaves(r.left)+numLeaves(r.right);
}

int numNodes(BNode <E> r)  /* funkcija koja go vrakja brojot na vnatreshni jazli */
{
    if(r==null) return 0; //ako stigneme do kraj na nekoe poddrvo
    if(r.left==null && r.right==null) //ako stigneme do list
        return 0;
    else
        return 1+numNodes(r.left)+numNodes(r.right);
}

int allNodes(BNode <E> r)  /* funkcija koja go vrakja vkupniot broj na jazli */
{
    if(r==null) return 0;
    return 1+allNodes(r.left)+allNodes(r.right);
}

}
public class BinarySearchTree {


    public static BNode<Integer> makeTreeOfArray(int a[], int l, int r)
        {
             if(l > r)
                 return null;
             BNode<Integer> result = new BNode<Integer>(a[(l+r)/2]);
             result.left = makeTreeOfArray(a,l,(l+r)/2-1);
             result.right = makeTreeOfArray(a,(l+r)/2+1,r);
             return result;
        }

    public static void main(String[] args) {

        BSTree <Integer> tree = new BSTree();
        int array [] = {1, 2, 4, 6, 7, 10, 15};

        tree.root = makeTreeOfArray(array,0,array.length-1);
    }
}