package edu.oakland.OUSoft.BST;

import java.util.Iterator;

public class cseBST<E extends Comparable<E>> implements Iterable<E> {
	
	private Node<E> root;
	
	public boolean contains(E o) {
		return containsRecurse(root, o);
	}
	
	private boolean containsRecurse(Node<E> node, E e) {
		if (node == null || e == null) {
			return false;
		}
		if (node.element.equals(e)) {
			return true;
		} else {
			if (e.compareTo(node.element) <= 0) {
				return containsRecurse(node.left, e);
			} else {
				return containsRecurse(node.right, e);
			}
		}
	}
	
	public boolean add(E e) {
		root = addRecurse(root, e);
		return true;
	}
	
	private Node<E> addRecurse(Node<E> node, E e) {
		if (node == null) {
			return new Node<>(e);
		} else if (e.compareTo(node.element) <= 0) {
			node.left = addRecurse(node.left, e);
		} else {
			node.right = addRecurse(node.right, e);
		}
		return node;
	}
	
	public void remove(E e) {
		root = removeRecurse(root, e);
	}
	
	private Node<E> removeRecurse(Node<E> node, E e) {
		if (node == null) {
			return null;
		}
		if (e.compareTo(node.element) < 0) {
			node.left = removeRecurse(node.left, e);
		} else if (e.compareTo(node.element) > 0) {
			node.right = removeRecurse(node.right, e);
		} else {
			node = removeNode(node);
		}
		return node;
	}
	
	private Node<E> removeNode(Node<E> node) {
		if (node.left == null) {
			return node.right;
		} else if (node.right == null) {
			return node.left;
		} else {
			Node<E> predecessor = getPredecessor(node.left);
			node.element = predecessor.element;
			node.left = removeRecurse(node.left, node.element);
			return node;
		}
	}
	
	private Node<E> getPredecessor(Node<E> node) {
		while (node.right != null) {
			node = node.right;
		}
		return node;
	}
	
	public int size() {
		return sizeRecurse(root);
	}
	
	private int sizeRecurse(Node<E> node) {
		if (node == null) {
			return 0;
		}
		return sizeRecurse(node.left) + sizeRecurse(node.right) + 1;
	}
	
	public boolean isEmpty() {
		return root == null;
	}
	
	public void clear() {
		root = null;
	}
	
	/**
	 * Returns an iterator over elements using Inorder method
	 *
	 * @return an Iterator.
	 */
	@Override
	public Iterator<E> iterator() {
		return new Iterator<E>() {
			Node<E> node = root;
			
			@Override
			public boolean hasNext() {
				return false;
			}
			
			@Override
			public E next() {
				return null;
			}
		};
	}
	
	private class Node<E> {
		E element;
		Node<E> left;
		Node<E> right;
		
		public Node(E e) {
			this.element = e;
		}
	}
	
}

@@ -30,36 +30,8 @@
 T;%0A%0A
-import java.util.Iterator;%0A%0A
 publ
@@ -74,31 +74,8 @@
 %3CE%3E%3E
- implements Iterable%3CE%3E
  %7B%0A%09
@@ -1990,343 +1990,8 @@
 %7D%0A%09%0A
-%09/**%0A%09 * Returns an iterator over elements using Inorder method%0A%09 *%0A%09 * @return an Iterator.%0A%09 */%0A%09@Override%0A%09public Iterator%3CE%3E iterator() %7B%0A%09%09return new Iterator%3CE%3E() %7B%0A%09%09%09Node%3CE%3E node = root;%0A%09%09%09%0A%09%09%09@Override%0A%09%09%09public boolean hasNext() %7B%0A%09%09%09%09return false;%0A%09%09%09%7D%0A%09%09%09%0A%09%09%09@Override%0A%09%09%09public E next() %7B%0A%09%09%09%09return null;%0A%09%09%09%7D%0A%09%09%7D;%0A%09%7D%0A%09%0A
 %09pri

Remove iterator