public class BST<E> implements Tree<E> {
  protected TreeNode<E> root;
  protected int size = 0;
  protected java.util.Comparator<E> c;

  /** Tworzy domyślne drzewo BST z komparatorem opartym na porządku naturalnym */
  public BST() {
    this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
  }

  /** Tworzenie drzewa BST z określonym komparatorem */
  public BST(java.util.Comparator<E> c) {
    this.c = c;
  }

  /** Tworzenie drzewa binarnego na podstawie tablicy obiektów */
  public BST(E[] objects) {
    this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
    for (int i = 0; i < objects.length; i++)
      add(objects[i]);
  }

  @Override /** Zwraca true, jeśli element znajduje się w drzewie */
  public boolean search(E e) {
    TreeNode<E> current = root; // Rozpoczynanie od korzenia

    while (current != null) {
      if (c.compare(e, current.element) < 0) {
        current = current.left;
      }
      else if (c.compare(e, current.element) > 0) {
        current = current.right;
      }
      else // Element pasuje to current.element
        return true; // Element został znaleziony
    }

    return false;
  }

  @Override /** Wstawianie elementu e do drzewa binarnego.
   * Zwraca true po udanym wstawieniu elementu */
  public boolean insert(E e) {
    if (root == null)
      root = createNewNode(e); // Tworzy nowy korzeń
    else {
      // Znajdowanie rodzica
      TreeNode<E> parent = null;
      TreeNode<E> current = root;
      while (current != null)
        if (c.compare(e, current.element) < 0) {
          parent = current;
          current = current.left;
        }
        else if (c.compare(e, current.element) > 0) {
          parent = current;
          current = current.right;
        }
        else
          return false; // Powtarzający się węzeł nie jest wstawiany

      // Tworzenie nowego węzła i dołączanie go do rodzica
      if (c.compare(e, parent.element) < 0)
        parent.left = createNewNode(e);
      else
        parent.right = createNewNode(e);
    }

    size++;
    return true; // Element został poprawnie wstawiony
  }

  protected TreeNode<E> createNewNode(E e) {
    return new TreeNode<>(e);
  }

  @Override /** Odwiedzanie węzłów od korzenia metodą inorder */
  public void inorder() {
    inorder(root);
  }

  /** Odwiedzanie węzłów od poddrzewa metodą inorder */
  protected void inorder(TreeNode<E> root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.element + " ");
    inorder(root.right);
  }

  @Override /** Odwiedzanie węzłów od korzenia metodą postorder */
  public void postorder() {
    postorder(root);
  }

  /** Odwiedzanie węzłów od poddrzewa metodą postorder */
  protected void postorder(TreeNode<E> root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.element + " ");
  }

  @Override /** Odwiedzanie węzłów od korzenia metodą preorder */
  public void preorder() {
    preorder(root);
  }

  /** Odwiedzanie węzłów od poddrzewa metodą preorder */
  protected void preorder(TreeNode<E> root) {
    if (root == null) return;
    System.out.print(root.element + " ");
    preorder(root.left);
    preorder(root.right);
  }

  /** Klasa wewnętrzna jest statyczna, ponieważ nie używa
      żadnych składowych instancji zdefiniowanych w klasie zewnętrznej */
  public static class TreeNode<E> {
    protected E element;
    protected TreeNode<E> left;
    protected TreeNode<E> right;

    public TreeNode(E e) {
      element = e;
    }
  }

  @Override /** Pobieranie liczby węzłów w drzewie */
  public int getSize() {
    return size;
  }

  /** Zwraca korzeń drzewa */
  public TreeNode<E> getRoot() {
    return root;
  }

  /** Zwraca ścieżkę z korzenia do określonego elementu */
  public java.util.ArrayList<TreeNode<E>> path(E e) {
    java.util.ArrayList<TreeNode<E>> list =
      new java.util.ArrayList<>();
    TreeNode<E> current = root; // Rozpoczynanie od korzenia

    while (current != null) {
      list.add(current); // Dodawanie węzła do listy
      if (c.compare(e, current.element) < 0) {
        current = current.left;
      }
      else if (c.compare(e, current.element) > 0) {
        current = current.right;
      }
      else
        break;
    }

    return list; // Zwraca kolekcji ArrayList węzłów
  }

  @Override /** Usuwanie elementu z drzewa binarnego.
   * Zwraca true po udanym usunięciu elementu.
   * Zwraca false, jeśli elementu nie ma w drzewie */
  public boolean delete(E e) {
    // Znajdowanie usuwanego węzła i jego rodzica
    TreeNode<E> parent = null;
    TreeNode<E> current = root;
    while (current != null) {
      if (c.compare(e, current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (c.compare(e, current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else
        break; // Element znajduje się w drzewie wskazywanym przez current
    }

    if (current == null)
      return false; // Elementu nie ma w drzewie

    // Scenariusz 1. current nie ma lewego dziecka
    if (current.left == null) {
      // Łączenie rodzica z prawym dzieckiem węzła current
      if (parent == null) {
        root = current.right;
      }
      else {
        if (c.compare(e, parent.element) < 0)
          parent.left = current.right;
        else
          parent.right = current.right;
      }
    }
    else {
      // Scenariusz 2. Węzeł current ma lewe dziecko.
      // Szukanie pierwszego od prawej węzła w lewym poddrzewie węzła
      // current i rodzica
      TreeNode<E> parentOfRightMost = current;
      TreeNode<E> rightMost = current.left;

      while (rightMost.right != null) {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right; // Przechodzenie w prawo
      }

      // Zastępowanie elementu w węźle current elementem z węzła rightMost
      current.element = rightMost.element;

      // Usuwanie węzła rightMost
      if (parentOfRightMost.right == rightMost)
        parentOfRightMost.right = rightMost.left;
      else
        // Specjalny przypadek: parentOfRightMost == current
        parentOfRightMost.left = rightMost.left;
    }

    size--; // Zmniejszanie wielkości drzewa
    return true; // Element został usunięty
  }

  @Override /** Pobieranie iteratora. Używanie porządku inorder. */
  public java.util.Iterator<E> iterator() {
    return new InorderIterator();
  }

  // Klasa wewnętrzna InorderIterator
  private class InorderIterator implements java.util.Iterator<E> {
    // Zapisywanie elementów na liście
    private java.util.ArrayList<E> list =
      new java.util.ArrayList<>();
    private int current = 0; // Bieżący element

    public InorderIterator() {
      inorder(); // Przechodzenie drzewa binarnego i zapisywanie elementów na liście
    }

    /** Odwiedzanie elementów od korzenia w porządku inorder */
    private void inorder() {
      inorder(root);
    }

    /** Odwiedzanie elementów od poddrzewa w porządku inorder */
    private void inorder(TreeNode<E> root) {
      if (root == null) return;
      inorder(root.left);
      list.add(root.element);
      inorder(root.right);
    }

    @Override /** Pozostały elementy do odwiedzenia? */
    public boolean hasNext() {
      if (current < list.size())
        return true;

      return false;
    }

    @Override /** Pobieranie bieżącego elementu i przechodzenie do następnego */
    public E next() {
      return list.get(current++);
    }

    @Override // Usuwanie elementu zwróconego przez ostatnie wywołanie next()
    public void remove() {
      if (current == 0) // Metoda next() nie została jeszcze wywołana
        throw new IllegalStateException();

      delete(list.get(--current));
      list.clear(); // Opróżnianie listy
      inorder(); // Ponowne tworzenie listy
    }
  }

  @Override /** Usuwanie wszystkich elementów drzewa */
  public void clear() {
    root = null;
    size = 0;
  }
}
