• Dr. Taylor's Page
• Calendar
• Policy
• Resources

Binary Search Trees

We've learned a lot of things about trees, but we haven't actually put any data in them yet. In a Binary Search Tree, we require that our data be sortable, and the rule is this: everything in the left subtree of a node is less than the node's data, and everything in the right subtree is greater. Pretty simple, right?

Here's some code to make that happen. insert() adds data to the tree, and find() returns a boolean as to whether that data appears in the tree.

public class BST {
  private class Node {
    private int data;
    private Node left, right;
    public Node(int data) { this.data = data; left = right = null; }
    public int getData() { return data; }
    public Node getLeft() { return left; }
    public Node getRight() { return right; }
    public void setLeft(Node left) { this.left = left; }
    public void setRight(Node right) { this.right = right; }
  }

  private Node root;

  public BST(){
    root = null;
  }
  
  public boolean find(int i) {
    return find(root, i);
  }
  private boolean find(Node n, int i) {
    if (n==null)
      return false;
    if (i == n.getData())
      return true;
    if (i < n.getData())
      return find(n.getLeft(), i);
    return find(n.getRight(), i);
  }

  public void insert(int i) {
    root = insert(root, i);
  }
  private Node insert(Node n, int i) {
    if (n==null)
      return new Node(i);
    if (i < n.getData())
      n.setLeft( insert(n.getLeft(), i) );
    else
      n.setRight( insert(n.getRight(), i) );
    return n;
  }
}

Method Runtime

Note that we do not know the height of a BST, except to say that it is somewhere between O(log(n)) and O(n), which is a massive range. The best we can say, is that both of these are O(height).