UNB/ CS/ David Bremner/ teaching/ java/ BinarySearchTree.java
```import java.lang.Math;
import java.util.Vector;
/**
This class implements a binary search tree whose
nodes hold objects that implement the Comparable
interface.
*/
class Node<U extends Comparable<U>>
{
public U data;
public Node<U> left, right;
public Node(U obj){
data = obj;
left = right = null;
}
/**
Inserts a new node as a descendant of this node.
@param newNode the node to insert
*/
public void insertNode(Node<U> newNode)
{
if (newNode.data.compareTo(data) < 0) {
if (left == null)
left = newNode;
else
left.insertNode(newNode);
} else {
if (right == null)
right = newNode;
else
right.insertNode(newNode);
}
}
/**
Prints this node and all of its descendants
in sorted order.
*/
public void printNodes() {
if (left != null)
left.printNodes();
System.out.println(data);
if (right != null)
right.printNodes();
}
public boolean search(U key){
System.out.println("Checking "+data);
int cval = data.compareTo(key);
if (cval == 0) {
return true;
} else if (cval > 0) {
if  (left == null)
return false;
else
return left.search(key);
} else {
if (right == null)
return false;
else
return right.search(key);
}
}

public int depth(){
int rdepth =
(right==null) ? 0 : right.depth();
int ldepth =
(left==null) ? 0 : left.depth();

return 1 + Math.max(rdepth, ldepth);
}

public U first(){
if (left == null)
return data;
else
return left.first();
}

public U last(){
if (right == null)
return data;
else
return right.last();
}

}

public class BinarySearchTree
<T extends Comparable<T>> {
private Node<T> root;
public BinarySearchTree() {
root = null;
}
/**
Inserts a new node into the tree.
@param obj the object to insert
*/
public void insert(T obj)
{
Node<T> newNode = new Node<T>(obj);
if (root == null)
root = newNode;
else
root.insertNode(newNode);
}
/**
Prints the contents of the tree in sorted order.
*/
public void print()
{
if (root != null)
root.printNodes();
}

static public <U extends Comparable<U>>
BinarySearchTree<U> fromSorted(Vector<U> items){

BinarySearchTree<U> tree= new BinarySearchTree<U>();

tree.root=BinarySearchTree.fromSorted(items,0,items.size()-1);
return tree;
}

static private <U extends Comparable<U>>
Node<U> fromSorted(Vector<U> items,  int first, int last){
if (first > last)
return null;

int mid = (first + last)/2;

Node<U> root = new Node<U>(items.elementAt(mid));

root.left=fromSorted(items,first,mid-1);
root.right=fromSorted(items,mid+1,last);
return root;
}

public boolean search(T key){
if (root == null)
return false;
else
return root.search(key);
}

public int depth(){
return (root==null) ? 0 : root.depth();
}

public T first(){
return (root==null) ?  null : root.first();
}

public T last(){
return (root==null) ?  null : root.last();
}

public static void main(String[] args)    {
BinarySearchTree<String> staff
= new BinarySearchTree<String>();

staff.insert("Romeo");
staff.insert("Juliet");
staff.insert("Tom");
staff.insert("Dick");
staff.insert("Harry");

staff.print();
}
}

```