/*
* File: BinarySearchTree.java
* Date: Dec 21, 2016
* Student: Devang Doshi | UCID: dbd24
* Course: Programming, Data Structure, and Alogrithms | Section: CS50581
* Desc: Implementation of Binary Search Tree.
/**
*
* @author Devang
*/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class BinarySearchTree> extends BinaryTree {
public Node getRoot(){
return root;
}
@Override
public void insert(E data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else {
InsertHelper(root, newNode);
}
}
private void InsertHelper(Node node, Node newNode) {
int compareResult = node.data.compareTo(newNode.data);
if (compareResult <= 0) {
if (node.right == null) {
node.right = newNode;
} else {
InsertHelper(node.right, newNode);
}
} else {
if (node.left == null) {
node.left = newNode;
} else {
InsertHelper(node.left, newNode);
}
}
}
@Override
public void remove(E key) {
root = RemoveHelper(root, key);
}
private E findMinimum(Node node) {
if (node.left == null) return node.data;
return findMinimum(node.left);
}
private Node RemoveHelper(Node node, E key) {
int compareResult = node.data.compareTo(key);
if (compareResult < 0) {
node.right = RemoveHelper(node.right, key);
} else if (compareResult > 0) {
node.left = RemoveHelper(node.left, key);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
E minValue = findMinimum(node.right);
node.data = minValue;
RemoveHelper(node.right, minValue);
}
return node;
}
@Override
public boolean search(E key) {
return SearchHelper(this.root, key);
}
private boolean SearchHelper(Node node, E key) {
if (node == null) return false;
int compareResult = node.data.compareTo(key);
if (compareResult == 0) return true;
return compareResult < 0 ? SearchHelper(node.right, key) : SearchHelper(node.left, key);
}
public class BinarySearchTreeIterator implements Iterator {
private List elements = new ArrayList();
private int index = 0;
public BinarySearchTreeIterator(BinarySearchTree tree)
{
InOrder(tree.getRoot());
}
private void InOrder(Node node) {
if (node == null) return;
InOrder(node.left);
elements.add(node.data);
InOrder(node.right);
}
@Override
public boolean hasNext() {
return (index < elements.size());
}
@Override
public E next() {
if(!hasNext()) return null;
E temp = elements.get(index);
index++;
return temp;
}
@Override
public void remove() {
}
}
public Iterator iterator() {
return new BinarySearchTreeIterator(this);
}
}