BST

package adt.bst;

public class BSTImpl<T extends Comparable<T>> implements BST<T> {

   protected BSTNode<T> root;

   public BSTImpl() {
      root = new BSTNode<T>();
   }

   public BSTNode<T> getRoot() {
      return this.root;
   }

   @Override
   public boolean isEmpty() {
      return root.isEmpty();
   }

   @Override
   public int height() {
      return height(getRoot());
   }

   private int height(BSTNode<T> no) {
       int ans = -1;
       if(!no.isEmpty()) {
          ans = Math.max(this.height((BSTNode<T>)no.getLeft()), this.height((BSTNode<T>)no.getRight())) + 1;
       }
       return ans;
   }

   @Override
   public BSTNode<T> search(T element) {
      BSTNode<T> ans = new BSTNode<T>();
      if(element != null && !isEmpty()) {
          ans = search(this.root, element);
      }
      return ans;
   }

   private BSTNode<T> search(BSTNode<T> no, T element) {
       if(!no.isEmpty()) {
          int igual = no.getData().compareTo(element);
          if(igual == 0) return no;
          if (igual < 0)
             return search((BSTNode<T>) no.getRight(), element);
          if (igual > 0)
             return search((BSTNode<T>) no.getLeft(), element);
      }
      return new BSTNode<T>();
   }

   @Override
   public void insert(T element) {
       if(element != null) {
           insert(getRoot(), element);
       }
   }

   private void insert(BSTNode<T> no, T element) {
      if (no.isEmpty()) {
        no.setData(element);
        no.setLeft(new BSTNode<T>());
        no.setRight(new BSTNode<T>());
        no.getLeft().setParent(no);
        no.getRight().setParent(no);
     } else {
        if(no.getData().compareTo(element) > 0) {
            this.insert((BSTNode<T>) no.getLeft(), element);
        }else if(no.getData().compareTo(element) < 0) {
            this.insert((BSTNode<T>) no.getRight(), element);
        }
     }
   }

   @Override
   public BSTNode<T> maximum() {
       BSTNode<T> ans = null;
       if(!getRoot().isEmpty()) ans = maximum(getRoot());
       return ans;
   }

   private BSTNode<T> maximum(BSTNode no) {
      if (no.getRight().isEmpty()) return no;
      return maximum((BSTNode<T>) no.getRight());
   }

   @Override
   public BSTNode<T> minimum() {
       BSTNode<T> ans = null;
       if(!isEmpty()) ans = minimum(this.root);
       return ans;
   }

   private BSTNode<T> minimum(BSTNode no) {
      if (no.getLeft().isEmpty()) return no;
      return minimum((BSTNode<T>) no.getLeft());
   }

   private BSTNode<T> alternativeParent(BSTNode<T> no, T element, boolean tipo){
       BSTNode<T> dad = (BSTNode<T>) no.getParent();
       if((dad == null || dad.getData().compareTo(element) < 0) && !tipo) return dad;
       if((dad == null || dad.getData().compareTo(element) > 0) && tipo) return dad;

       return alternativeParent(dad, element, tipo);
   }

   @Override
   public BSTNode<T> sucessor(T element) {
      BSTNode<T> ans = null;
      if (element != null) {
         BSTNode<T> no = search(element);
         if(!no.isEmpty()) {
             if (!no.getRight().isEmpty()) {
                ans = minimum((BSTNode<T>) no.getRight());
            }else {
                ans = alternativeParent(no, no.getData(), true);
            }
         }
      }
      return ans;
   }

   @Override
   public BSTNode<T> predecessor(T element) {
       BSTNode<T> ans = null;
       if (element != null) {
           BSTNode<T> no = search(element);
           if(!no.isEmpty()) {
               if (!no.getLeft().isEmpty()) {
                   ans = maximum((BSTNode<T>) no.getLeft());
               }else {
                   ans = alternativeParent(no, element, false);
               }
           }
       }
       return ans;
   }

   @Override
   public void remove(T element) {
      if (element != null) {
         BSTNode<T> no = search(element);
         remove(no);
      }
   }

   private void remove(BSTNode<T> no) {
      if(!no.isEmpty()) {
          if(no.isLeaf()) {
              replace(no, new BSTNode());
          }else if(no.getRight().isEmpty()) {
              replace(no,(BSTNode<T>) no.getLeft());
          }else if(no.getLeft().isEmpty()) {
              replace(no, (BSTNode<T>) no.getRight());
          }else {
              BSTNode<T> sucess = sucessor(no.getData());
              System.out.println(sucess.getData());
              no.setData(sucess.getData());
              remove(sucess);
          }
      }
   }

   private void replace(BSTNode<T> no, BSTNode<T> set) {
       BSTNode<T> dad = (BSTNode<T>)no.getParent();
       if(dad == null) {
           this.root = set;
           set.setParent(null);
       }else {
          if(dad.getData().compareTo(no.getData()) <= 0) {
              dad.setRight(set);
              dad.getRight().setParent(dad);
          }else {
              dad.setLeft(set);
              dad.getLeft().setParent(dad);
          }
       }
   }

   @Override
   public T[] preOrder() {
      T[] arr = (T[]) new Comparable[this.size()];
      if(!this.isEmpty()) preOrder(this.root, arr, 0);
      return arr;
   }

   private int preOrder(BSTNode<T> no, T[] arr, int idx) {
       if(!no.isEmpty()) {
          arr[idx++] = no.getData();
          idx = preOrder((BSTNode<T>) no.getLeft(), arr, idx);
          idx = preOrder((BSTNode<T>) no.getRight(), arr, idx);
       }
       return idx;
   }

   @Override
   public T[] order() {
      T[] arr = (T[]) new Comparable[this.size()];
      if(!this.isEmpty())order(getRoot(), arr, 0);

      return arr;
   }

   private int order(BSTNode<T> no, T[] arr, int idx) {
       if(!no.isEmpty()) {
          idx = order((BSTNode<T>) no.getLeft(), arr, idx);
          arr[idx++] = no.getData();
          idx = order((BSTNode<T>) no.getRight(), arr, idx);
       }
       return idx;
   }

   @Override
   public T[] postOrder() {
      T[] arr = (T[]) new Comparable[this.size()];
      if(!this.isEmpty()) postOrder(getRoot(), arr, 0);

      return arr;
   }

   private int postOrder(BSTNode no, T[] arr, int idx) {
       if(!no.isEmpty()) {
          idx = postOrder((BSTNode<T>) no.getLeft(), arr, idx);
          idx = postOrder((BSTNode<T>) no.getRight(), arr, idx);
          arr[idx++] = (T) no.getData();
       }
       return idx;
   }

   /**
    * This method is already implemented using recursion. You must understand
    * how it work and use similar idea with the other methods.
    */
   @Override
   public int size() {
      return size(root);
   }

   private int size(BSTNode<T> node) {
      int result = 0;
      // base case means doing nothing (return 0)
      if (!node.isEmpty()) { // indusctive case
         result = 1 + size((BSTNode<T>) node.getLeft()) + size((BSTNode<T>) node.getRight());
      }
      return result;
   }

}