# teaching machines

## CS 245 Lecture 25 – Binary Search Tree Add, Traverse

### Agenda

• what ?s
• schedule
• homework (* this week, 1 next week, 1 during finals)
• last lab tomorrow
• final: Friday at 1 PM
• hw3 demo
• adding nodes to a BST
• iterating through a BST
• deleting nodes from a BST

### Code

#### KeyValueVisitor.java

package lecture25;

public interface KeyValueVisitor<K, V> {
public void visit(K key, V value, int level);
}

#### BinarySearchTree.java

package lecture25;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class BinarySearchTree<K extends Comparable<K>, V> {
private Node<K, V> root;

public BinarySearchTree() {
root = null;
}

public boolean isEmpty() {
return root == null;
}

public int size() {
return size(root);
}

private int size(Node<K, V> startingNode) {
// Base case: when startingNode is null
if (startingNode == null) {
return 0;
}

// General case: when startingNode is not null
else {
return 1 + size(startingNode.left) + size(startingNode.right);
}
}

public V get(K key) {
return get(key, root);
}

private V get(K key,
Node<K, V> startingNode) {
if (startingNode == null) {
throw new NoSuchElementException("No value for key " + key);
} else {
int order = key.compareTo(startingNode.key);
if (order == 0) {
return startingNode.value;
} else if (order < 0) {
return get(key, startingNode.left);
} else {
return get(key, startingNode.right);
}
}
}

V value) {
}

private Node<K, V> subtreeByAdding(Node<K, V> startingNode,
K key,
V value) {
Node<K, V> subtreeRoot;

// We hit paydirt!
if (startingNode == null) {
subtreeRoot = new Node<K, V>(key, value, null, null);
}

// The subtree we're trying to insert into is non-empty. A couple
// of things may be true. The new item might belong in one of this
// node's subtrees. Or it may match the node itself.
else {
int order = key.compareTo(startingNode.key);
subtreeRoot = startingNode;

// Thing to insert appears left of pivot point! Blam!
if (order < 0) {
}

// Thing to insert appears right of pivot point! Whap!
else if (order > 0) {
}

// The keys are the same. Oh oh oh.
else {
startingNode.value = value;
}
}

return subtreeRoot;
}

public void traversePreorder(KeyValueVisitor<K, V> visitor) {
traversePreorder(root, visitor, 0);
}

private void traversePreorder(Node<K, V> startingNode, KeyValueVisitor<K, V> visitor, int level) {
if (startingNode != null) {
visitor.visit(startingNode.key, startingNode.value, level);
traversePreorder(startingNode.left, visitor, level + 1);
traversePreorder(startingNode.right, visitor, level + 1);
}
}

private static class Node<K, V> {
K key;
V value;

Node<K, V> left;
Node<K, V> right;

public Node(K key,
V value,
Node<K, V> left,
Node<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}

public static void main(String[] args) throws FileNotFoundException {
BinarySearchTree<Integer, String> tree = new BinarySearchTree<Integer, String>();

tree.traversePreorder(new KeyValueVisitor<Integer, String>() {
@Override
public void visit(Integer key,
String value,
int level) {
System.out.println(getSpace(level) + key + " -> " + value);
}
});
}

private static String getSpace(int nspaces) {
String s = "";
for (int i = 0; i < nspaces; ++i) {
s += " ";
}
return s;
}
}