package BTree;

public class BinaryTree implements Tree {
	//Data
	protected TreeNode root;

	//Constructors
  	public BinaryTree() { this(null); }
  	public BinaryTree(TreeNode n) { root = n; }
	
	//Access methods
	public TreeNode getRoot() { return root; }
	
	public BinaryTree getLeftSubtree() {
		return isEmpty() ? null : new BinaryTree(root.left);
	}
	
	public BinaryTree getRightSubtree() {
		return isEmpty() ? null : new BinaryTree(root.right);
	}
	
  	//Tree methods
  	public void add(Object element) {
  		if(isEmpty()) root = new TreeNode(element);
    	else {
      		int w = (int)(100.0 * Math.random()) % 2;
      		if( w == 0)
           		if(root.left == null) root.left = new TreeNode(element);
           		else getLeftSubtree().add(element);
      		else
           		if(root.right == null) root.right = new TreeNode(element);
           		else getRightSubtree().add(element);
    	}
  	}
  	
  	public Object remove(Object element) {
  		throw new UnsupportedOperationException();
  	}
  	
  	public boolean contains(Object element) {
  		if(isEmpty()) return false;
  		if(root.data.equals(element)) return true;
  		return getLeftSubtree().contains(element) ?
  						true : getRightSubtree().contains(element);
  	}
    
  	public boolean isEmpty() { return root == null; }

	public int size() {
  		return isEmpty() ? 
  			0 : getLeftSubtree().size() + 1 + getRightSubtree().size();
 	}
 	
	public int height() {
		return isEmpty() ? 
			-1 : Math.max(getLeftSubtree().height(),getRightSubtree().height()) + 1;

	}
	
	public int numberOfLiefs() {
		if(isEmpty()) return 0;
		BinaryTree leftTree = getLeftSubtree();
		BinaryTree rightTree = getRightSubtree();
		return leftTree.isEmpty() && rightTree.isEmpty() ? 
			1 : leftTree.numberOfLiefs() + rightTree.numberOfLiefs();
	}
	
	public void clear() { root = null; }
			
	public java.util.Iterator iterator() {
		return new BTreeInorderIterator(this); 
	}
	public java.util.Iterator treeInorderIterator() {
		return new BTreeInorderIterator(this);
	}
	public java.util.Iterator treePreorderIterator() {
		return new BTreePreorderIterator(this);
	}
	public java.util.Iterator treePostorderIterator() {
		return new BTreePostorderIterator(this);
	}
  	public java.util.Iterator treeBreadthFirstIterator() {
  		return new BTreeBreadthFirstIterator(this);
  	}
	
  	public Object clone() { 
  		//return new BinaryTree(this.copy(new BinaryTree()));
  		if(!this.isEmpty()) {
  			BinaryTree tree = new BinaryTree(new TreeNode(this.root.data));
  			tree.root.left = ((BinaryTree)(this.getLeftSubtree().clone())).root;
  			tree.root.right = ((BinaryTree)(this.getRightSubtree().clone())).root;
  			return tree;
  		}
		return new BinaryTree();
  	}
 
  	public String toString() {
  		if(!this.isEmpty()) {
  			String str = "\n" + this.root.data() + ": ";
  			str = str + (this.root.left != null ? this.root.left.data : "null") + ", ";
  			str = str + (this.root.right != null ? this.root.right.data : "null");
  			str = str + this.getLeftSubtree().toString();
  			str = str + this.getRightSubtree().toString();
  			return str;
  		}
		return "";
  	}
}