package cse1030.datastructures;

/**
 * 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 CSE1030
 * 
 * @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 CSE1030
   * 
   * @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;
  }

  /**
   * 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;
  }

  /**
   * 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);
      }
    }
  }

  /**
   * Return a string representation of the inorder traversal 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;
  }

  
  /**
   * Returns a string representation of the preorder traversal 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.
   * 
   * @return a string representation of the preorder traversal of the tree
   */
  public String preOrder() {
    StringBuilder b = new StringBuilder();
    b.append('{');
    
    
    
    
    
    
    b.append('}');
    return b.toString();
  }

  
  /**
   * Returns a string representation of the breadth first search traversal 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 breadth first
   * search traversal for any node of the tree visits the node, followed by the
   * left child of the node, followed by the right child of the node.
   * 
   * @return a string representation of the breadth first search traversal of the tree
   */
  public String bfs() {
    StringBuilder b = new StringBuilder();
    b.append('{');
    
    
    
    
    
    
    
    b.append('}');
    return b.toString();
  }
  
  

  public static void main(String[] args) {
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
    t.add(50);
    t.add(25);
    t.add(75);
    t.add(12);
    t.add(35);
    t.add(40);
    t.add(60);
    t.add(85);
    t.add(95);
    System.out.println("inorder             : " + t.toString());
    System.out.println("preorder            : " + t.preOrder());
    System.out.println("breadth first search: " + t.bfs());
  }
}