public class BinarySearchTree<T extends Comparable<T>> implements SortedCollection<T> {

  protected BinaryTreeNode<T> root;
  /**
   * Constructor for a Binary Search Tree
   */
  public BinarySearchTree() {
    this.root = null;
  }

  /**
   * Inserts a new data value into the sorted collection
   * @param data the new value being inserted
   * @throws NullPointerException if data argument is null
   */
  @Override
  
public void insert(T data) throws NullPointerException {
    if (data == null) {
        throw new NullPointerException("Cannot insert null data.");
    }
    BinaryTreeNode<T> node = new BinaryTreeNode<>(data);

    // If tree is empty, insertHelper will set `root = node`.
    insertHelper(node, this.root);
}


  /**
   * Check whether data is stored in the tree
   * @param data the value to check for 
   * @return true if the collection contains data 
   */
  @Override
  public boolean contains(Comparable<T> data) {

    // return false if there is not data
    if (data == null) {
      return false;
    }

    BinaryTreeNode<T> current = root;
    while (current != null) {
      int comp = data.compareTo(current.getData());
      if (comp == 0) {
        return true;
      } else if (comp < 0) {
        current = current.childLeft();
      } else {
        current = current.childRight();
      }
    }
    return false;
  }

  /**
   * Counts the number of elements in the collection
   * @return the number of values in the collection
   */
  @Override
  public int size() {
    return findSize(root);
  }

  /**
   * Recursively finds the size of the tree 
   */
  private int findSize(BinaryTreeNode<T> node) {

    // Base case
    if (node == null) {
      return 0;
    }

    // Recursive Case
    return 1 +findSize(node.childLeft()) + findSize(node.childRight());
  }

  /**
   * Checks if the collection is empty
   * @return true if the tree is empty
   */
  @Override
  public boolean isEmpty() {
    return root == null;
  }

  /**
   * Removes all values and duplicates from the collection
   */
  @Override
  public void clear() {
    root = null;
  }

  /**
   * Helper method to insert a new node into the BST
   *
   * @param newNode the node to be inserted
   * @param subtree the subtree in which to insert the node
   */
  protected void insertHelper(BinaryTreeNode<T> newNode, BinaryTreeNode<T> subtree) {
    // If subtree is null, it means we've found the spot to insert in an empty tree.
    if (subtree == null) {
        this.root = newNode;  // The new node becomes the root of the whole tree.
        return;
    }

    // Compare to decide whether to go left or right.
    if (newNode.getData().compareTo(subtree.getData()) > 0) {
        if (subtree.childRight() == null) {
            subtree.setChildRight(newNode);
            newNode.setParent(subtree);
        } else {
            insertHelper(newNode, subtree.childRight());
        }
    } else {
        if (subtree.childLeft() == null) {
            subtree.setChildLeft(newNode);
            newNode.setParent(subtree);
        } else {
            insertHelper(newNode, subtree.childLeft());
        }
    }
}


  /**
   * A tester for the methods in the BinarySearchTree class
   * @return true if all methods pass the tests included within this method.
   */
  public boolean test1() {
    BinarySearchTree<Integer> BST = new BinarySearchTree<>();
    BST.insert(20);
    BST.insert(15);
    BST.insert(25);
    BST.insert(10);
    BST.insert(17);
    BST.insert(22);
    BST.insert(30);

    if (!(BST.contains(20) && BST.contains(15) && BST.contains(25) &&
          BST.contains(10) && BST.contains(17) && BST.contains(22) &&
          BST.contains(30))) {
      return false;
    }

    if (BST.size() != 7) {
      return false;
    }

    BST.clear();
    if (BST.size() != 0 || !BST.isEmpty()) {
      return false;
    }
    return true;
  }

  /**
   * A tester for the methods in the BinarySearchTree class using String values.
   * @return true if all methods pass the tests included within this method.
   */
  public boolean test2() {
    BinarySearchTree<String> BST = new BinarySearchTree<>();
    BST.insert("Sam");
    BST.insert("Wam");
    BST.insert("Jam");
    BST.insert("Ham");

    if (!(BST.contains("Sam") && BST.contains("Wam") &&
          BST.contains("Jam") && BST.contains("Ham"))) {
      return false;
    }

    if (BST.size() != 4) {
      return false;
    }

    BST.clear();
    if (BST.size() != 0 || !BST.isEmpty()) {
      return false;
    }
    return true;
  }

  /**
   * A tester for the methods in the BinarySearchTree class with integers.
   * @return true if all methods pass the tests included within this method.
   */
  public boolean test3() {
    BinarySearchTree<Integer> BST = new BinarySearchTree<>();
    BST.insert(1);
    BST.insert(2);
    BST.insert(3);
    BST.insert(4);
    BST.insert(5);
    BST.insert(6);
    BST.insert(7);

    if (!(BST.contains(1) && BST.contains(2) && BST.contains(3) &&
          BST.contains(4) && BST.contains(5) && BST.contains(6) &&
          BST.contains(7))) {
      return false;
    }

    if (BST.size() != 7) {
      return false;
    }

    BST.clear();
    if (BST.size() != 0 || !BST.isEmpty()) {
      return false;
    }
    return true;
  }

  /**
   * Main method for BinarySearchTree.java
   * @param args
   */
  public static void main(String[] args) {
    BinarySearchTree<Integer> testTree = new BinarySearchTree<>();
    System.out.println("Test 1: " + (testTree.test1() ? "PASSED" : "FAILED"));
    System.out.println("Test 2: " + (testTree.test2() ? "PASSED" : "FAILED"));
    System.out.println("Test 3: " + (testTree.test3() ? "PASSED" : "FAILED"));
  }
}