package cse1030.recursion;


/**
 * A binary search tree class.
 * 
 * <p>
 * A binary search tree is a binary tree where values are stored in the tree
 * according to three rules:
 * 
 * <ol>
 * <li>values in the left subtree are less than values in the root node
 * <li>values in the right subtree are greater than or equal to values in the
 * root node
 * <li>rules 1 and 2 apply recursively to every subtree
 * </ol>
 * 
 * @author CSE1030Z
 * 
 * @param <E> the type of the data stored in the nodes of the binary search tree
 */
public class BinarySearchTree<E extends Comparable<? super E>> {

  /**
   * A class that represents nodes in the binary search tree. Each
   * node stores a data element, and has a left and right child node.
   * This inner class is public for testing purposes only; normally,
   * Node would be a private inner class.
   * 
   * @author CSE1030Z
   *
   * @param <E>
   */
  public static class Node<E> {
    private E data;
    private Node<E> left;
    private Node<E> right;

    /**
     * Create a node with the given data element. The left
     * and right child nodes are set to null.
     * 
     * @param data the element to store
     */
    public Node(E data) {
      this.data = data;
      this.left = null;
      this.right = null;
    }
    
    /**
     * Get the left child node; for testing purposes only.
     * 
     * @return the left child node
     */
    public Node<E> left() {
      return this.left;
    }
    
    /**
     * Get the right child node; for testing purposes only.
     * 
     * @return the right child node
     */
    public Node<E> right() {
      return this.right;
    }
    
    
    /**
     * Get the data stored in the node; for testing purposes only.
     * 
     * @return the data stored in the node
     */
    public E data() {
      return this.data;
    }
  }

  /**
   * The root node of the binary search tree.
   */
  private Node<E> root;

  /**
   * Create an empty binary search tree.
   */
  public BinarySearchTree() {
    this.root = null;
  }

  /**
   * Add an element to the tree. The element is inserted into the tree in a
   * position that preserves the definition of a binary search tree.
   * 
   * @param element
   *          the element to add to the tree
   */
  public void add(E element) {
    if (this.root == null) {
      this.root = new Node<E>(element);
    } else {
      BinarySearchTree.add(element, this.root);
    }
  }

  /**
   * Add an element to the subtree rooted at <code>subtreeRoot</code>. The
   * element is inserted into the tree in a position that preserves the
   * definition of a binary search tree.
   * 
   * @param element
   *          the element to add to the subtree
   * @param subtreeRoot
   *          the root of the subtree
   */
  private static <E extends Comparable<? super E>>
  void add(E element, Node<E> subtreeRoot) {
    if (element.compareTo(subtreeRoot.data) < 0) {
      if (subtreeRoot.left == null) {
        subtreeRoot.left = new Node<E>(element);
      } else {
        BinarySearchTree.add(element, subtreeRoot.left);
      }
    } else {
      if (subtreeRoot.right == null) {
        subtreeRoot.right = new Node<E>(element);
      } else {
        BinarySearchTree.add(element, subtreeRoot.right);
      }
    }
  }

  /**
   * Returns <code>true</code> if the tree contains the given element,
   * <code>false</code> otherwise.
   * 
   * @param element
   *          the element to search for
   * @return <code>true</code> if the tree contains the given element,
   *         <code>false</code> otherwise
   */
  public boolean contains(E element) {
    return contains(element, this.root);
  }

  /**
   * Returns <code>true</code> if the subtree rooted at <code>subtreeRoot</code>
   * contains the given element, <code>false</code> otherwise.
   * 
   * @param element
   *          the element to search for
   * @param subtreeRoot
   *          the root of the subtree
   * @return <code>true</code> if the subtree rooted at <code>subtreeRoot</code>
   *         contains the given element, <code>false</code> otherwise
   */
  private static <E extends Comparable<? super E>>
  boolean contains(E element, Node<E> subtreeRoot) {
    if (subtreeRoot == null) {
      return false;
    }
    if (element.equals(subtreeRoot.data)) {
      return true;
    }
    boolean result;
    if (element.compareTo(subtreeRoot.data) < 0) {
      result = contains(element, subtreeRoot.left);
    } else {
      result = contains(element, subtreeRoot.right);
    }
    return result;
  }

  


  /**
   * Return a string representation of the tree.
   * 
   * <p>
   * The string is made up of the elements stored in the tree separated
   * by commas; the entire list of elements is enclosed in braces. The
   * elements are in ascending sorted order.
   * 
   * @see java.lang.Object#toString()
   *
   * @return a string representation of the tree
   */
  @Override
  public String toString() {
    return "{" + toString(this.root) + "}";
  }

  /**
   * Return a string representation of the subtree rooted at <code>subtreeRoot</code>.
   * 
   * <p>
   * The string is made up of the elements stored in the tree separated
   * by commas where the elements are in ascending sorted order.
   * 
   * <p>
   * The string is generated using inorder processing of the subtree:
   * 
   * <ol>
   * <li>the string corresponding to <code>subtreeRoot.left</code> is computed
   * <li>the string corresponding to <code>subtreeRoot.data</code> is computed
   * <li>the string corresponding to <code>subtreeRoot.right</code> is computed
   * </ol>
   * 
   * <p>
   * The returned string is the concatenation of the three strings computed by the
   * inorder processing of the subtree.
   * 
   * @param subtreeRoot the root of the subtree
   * @return the string representation of the subtree
   */
  private static <E> String toString(Node<E> subtreeRoot) {
    if (subtreeRoot == null) {
      return "";
    }
    String left = toString(subtreeRoot.left);
    if (!left.isEmpty()) {
      left = left + ", ";
    }
    String right = toString(subtreeRoot.right);
    if (!right.isEmpty()) {
      right = ", " + right;
    }
    return left + subtreeRoot.data + right;
  }
  
  /**
   * Get the root node of the tree. For testing purposes only.
   * 
   * @return the root node of the tree.
   */
  public Node<E> getRoot() {
    return this.root;
  }
  
  
  /**
   * Find the node in a subtree that has the smallest data element.
   * 
   * @param subtreeRoot the root of the subtree
   * @return the node in the subtree that has the smallest data element.
   */
  public static <E> Node<E> minimumInSubtree(Node<E> subtreeRoot) {
    if (subtreeRoot.left() == null) {
      return subtreeRoot;
    }
    return BinarySearchTree.minimumInSubtree(subtreeRoot.left()); 
  }
  
  /**
   * Find the node in a subtree that has the largest data element.
   * 
   * @param subtreeRoot the root of the subtree
   * @return the node in the subtree that has the largest data element.
   */
  public static <E> Node<E> maximumInSubtree(Node<E> subtreeRoot) {
    if (subtreeRoot.right() == null) {
      return subtreeRoot;
    }
    return BinarySearchTree.maximumInSubtree(subtreeRoot.right()); 
  }
  
  /**
   * Find the node in a subtree that is the predecessor to the root of the
   * subtree. If the predecessor node exists, then it is the node that has
   * the largest data element in the left subtree of <code>subtreeRoot</code>. 
   * 
   * @param subtreeRoot the root of the subtree
   * @return the node in a subtree that is the predecessor to the root of the
   * subtree, or <code>null</code> if the root of the subtree has no predecessor
   */
  public static <E> Node<E> predecessorInSubtree(Node<E> subtreeRoot) {
    if (subtreeRoot.left() == null) {
      return null;
    }
    return BinarySearchTree.maximumInSubtree(subtreeRoot.left()); 
  }
  
 
  /**
   * Find the node in a subtree that is the successor to the root of the
   * subtree. If the successor node exists, then it is the node that has
   * the smallest data element in the right subtree of <code>subtreeRoot</code>. 
   * 
   * @param subtreeRoot the root of the subtree
   * @return the node in a subtree that is the successor to the root of the
   * subtree, or <code>null</code> if the root of the subtree has no successor
   */
  public static <E> Node<E> successorInSubtree(Node<E> subtreeRoot) {
    if (subtreeRoot.right() == null) {
      return null;
    }
    return BinarySearchTree.minimumInSubtree(subtreeRoot.right()); 
  }
  
}