teaching machines

CS 245 Lecture 22 – Stacks and Binary Search Tree

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

Agenda

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

TODO

• Watch a random YouTube video on stacks and queues. Read about Java’s Stack badness. Read about using stacks and queues for time management. 1/4 sheet.

Design This

Program This

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);
    }
  }

  public void add(K key,
                  V value) {
    Node<K, V> nodeToAdd = new Node<K, V>(key, value, null, null);
    if (root == null) {
      root = nodeToAdd;
    } else {
      root.add(nodeToAdd);
    }
    ++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;
    }
    
    public void add(Node nodeToAdd) {
      
    }
  }
}

Haiku