import java.util.NoSuchElementException;
public class BinarySearchTree
private static class Node
private T value;
private Node
private Node
private Node(T value) {
this.value = value;
left = null;
right = null;
}
}
private Node
public boolean containsRec(E element) {
return containsRec(root, element);
}
private boolean containsRec(Node
boolean result;
if (current == null) {
result = false;
} else {
int test = element.compareTo(current.value);
if (test == 0 ) {
result = true;
} else if (test < 0) {
result = containsRec(current.left, element);
} else {
result = containsRec(current.right, element);
}
}
return result;
}
public boolean contains(E element) {
boolean found = false;
Node
while (! found && current != null) {
int test = element.compareTo(current.value);
if (test == 0) {
found = true;
} else if (test < 0) {
current = current.left;
} else {
current = current.right;
}
}
return found;
}
private void visit(Node
System.out.println(current.value);
}
public void preOrder() {
System.out.println(“preOrder()”);
preOrder(root);
System.out.println();
}
private void preOrder(Node
if (current != null) {
visit(current);
preOrder(current.left);
preOrder(current.right);
}
}
public void inOrder() {
System.out.println(“inOrder()”);
inOrder(root);
System.out.println();
}
private void inOrder(Node
if (current != null) {
inOrder(current.left);
visit(current);
inOrder(current.right);
}
}
public void postOrder() {
System.out.println(“postOrder()”);
postOrder(root);
System.out.println();
}
private void postOrder(Node
if (current != null) {
postOrder(current.left);
postOrder(current.right);
visit(current);
}
}
public void add(E element) {
if (root == null) {
root = new Node
} else {
Node
boolean done = false;
while (! done) {
int test = element.compareTo(current.value);
if (test == 0) {
done = true;
} else if (test < 0) {
if (current.left == null) {
current.left = new Node
done = true;
} else {
current = current.left;
}
} else {
if (current.right == null) {
current.right = new Node
done = true;
} else {
current = current.right;
}
}
}
}
}
public int size() {
return size(root);
}
private int size(Node
if (current == null) {
return 0;
}
return 1 + size(current.left) + size(current.right);
}
public boolean isLeaf(E element) {
boolean found = false;
Node
while (! found && current != null) {
int test = element.compareTo(current.value);
if (test == 0) {
found = true;
} else if (test < 0) {
current = current.left;
} else {
current = current.right;
}
}
if (! found) {
return false;
}
return current.left == null && current.right == null;
}
public String toString() {
return toString(root);
}
private String toString(Node
if (current == null) {
return “null”;
}
return “(“+toString(current.left)+”,”+current.value+”,”+toString(current.right)+”)”;
}
}