# teaching machines

## CS 245 Lecture 22 – Stacks and Binary Search Tree

April 17, 2014 by . Filed under cs245, lectures, spring 2014.

### Agenda

• what ?s
• the purpose of stacks and queues
• a postfix expression calculator
• binary search tree

### Design This

1. You are building a 2-D memory/matching game. When the user clicks on the screen, the clicked-upon card is flipped. What data structure would you use to facilitate this interaction?
2. You are writing an application that provides a command-line interface to applications on the computer. When the user types “ls”, the application stored at /usr/bin/ls is run. When the user types “octave”, the application stored at /usr/local/bin/octave is run. What data structure would you use to facilitate this interaction?
3. You have the finishing times from a large marathon. People are asking your application who the nth-place finisher was. What data structure would you use to facilitate this interaction?
4. You are writing a web browser and want to know if a URL has been visited before. If so, you can color it differently. What data structure would you use to achieve this effect?

### Program This

You’ve got an expression in “postfix” form:

• 1 2 + (which is 1 + 2)
• 3 6 * 5 – (which is 3 * 6 – 5)
• 60 12 / 2 ^ (which is (60 / 12) ^ 2)

Devise a plan to parse and evaluate such expressions.

### Code

#### BinarySearchTree.java

package lecture22;

public class BinarySearchTree<K, V> {
private Node<K, V> root;
private int size;

public BinarySearchTree() {
root = null;
size = 0;
}

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

private int size(Node<K, V> root) {
if (root == null) {
return 0;
} else {
return 1 + size(root.left) + size(root.right);
}
}

V value) {
Node<K, V> nodeToAdd = new Node<K, V>(key, value, null, null);
if (root == null) {
} else {
}
++size;
}

public static class Node<K, V> {
private K key;
private V value;
private Node<K, V> left;
private 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;
}

}