Binary Search Trees

Trees

Terminology

• Tree - A data structure which acts as a fully connected graph without loops
• Node - May contain data, has references to children nodes
• Each node may only have a single parent, but may have 0 or more children
• Edges - Link nodes together
• Root node - Node without any parent (the start of a tree)
• Leaf node - Node without children
• Inner (or interior) node - node that is not a root node or a leaf node
• Parent node - A node that references the current node
• Child node - A node that is referenced from current node
• Descendant node - Any node (including children) which descend from current node (i.e. children, grand children, etc)
• Sibling - Nodes are siblings if they have the same parent node
• Ancestor node - Nodes that come before the current node (parent, grandparent, etc)
• Height - the maximum distance of any node from the root (if a tree only has one node (the root), the height is 0
• Depth - Distance from a given node to the root of a tree
• Level - All the nodes of a tree with the same depth

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

In the above tree can you identify:

• The root node?
• The parent of 13?
• The children of 2?
• The descendants of 8?
• The ancestors of 22?
• The interior nodes?
• The leaf nodes?
• The sibling of 3?
• The depth of 1?

Binary Trees

• Every node may only have a maximum of two children nodes (hence the term binary)
• Full tree - Every node has either 0 or 2 children (or put another way, all nodes have 2 children except for leaf nodes)
• Perfect binary tree - Binary tree in which all leaves are at the same level
• Complete binary tree, similar to full tree, but any leaf nodes must be as left as possible in the tree

/**
 * A single binary tree node.
 * <p>
 * Each node has both a left or right child, which can be null.
 */
public class TreeNode<E> {

  private E data;
  private TreeNode<E> left;
  private TreeNode<E> right;

  /**
   * Constructs a new node with the given data and references to the
   * given left and right nodes.
   */
  public TreeNode(E data, TreeNode<E> left, TreeNode<E> right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  /**
   * Constructs a new node containing the given data.
   * Its left and right references will be set to null.
   */
  public TreeNode(E data) {
    this(data, null, null);
  }

  /** Returns the item currently stored in this node. */
  public E getData() {
    return data;
  }

  /** Overwrites the item stored in this Node with the given data item. */
  public void setData(E data) {
    this.data = data;
  }

  /**
   * Returns this Node's left child.
   * If there is no left left, returns null.
   */
  public TreeNode<E> getLeft() {
    return left;
  }

  /** Causes this Node to point to the given left child Node. */
  public void setLeft(TreeNode<E> left) {
    this.left = left;
  }

  /**
   * Returns this nodes right child.
   * If there is no right child, returns null.
   */
  public TreeNode<E> getRight() {
    return right;
  }

  /** Causes this Node to point to the given right child Node. */
  public void setRight(TreeNode<E> right) {
    this.right = right;
  }
}

Binary Search Trees

• A binary tree which keeps elements in sorted order
• Invariant: For every node, smaller values are in left subtree, larger are in right subtree (equal values are undefined and up to the implementation)
• Every insertion creates a new leaf node
• Every subtree within a BST is also a valid BST, thus a BST is a recursive structure

An empty BST

public class BinarySearchTree<E extends Comparable<E>> {
  private TreeNode<E> root;
  private int size;

  /** Creates an empty tree. */
  public BinarySearchTree() {
    this.root = null;
    this.size = 0;
  }

BST Search

• Start at root and recursively compare value we're searching for against current node
• If value is less than current node, recurse on left subtree
• If value is greater than current node, recurse on right subtree
• If recursion takes you to a leaf node, and the leaf node does not contain your value, then value is not in tree

/**
   * Returns first item from tree that is equivalent (according to compareTo)
   * to the given item.  If item is not in tree, returns null.
   */
  public E get(E item) {
    return get(item, this.root);
  }

  /** Finds it in the subtree rooted at the given node. */  
  private E get(E item, TreeNode<E> node) {
    if (node == null) {
      return null;
    }else if (item.compareTo(node.getData()) < 0) {
      return get(item, node.getLeft());
    }else if (item.compareTo(node.getData()) > 0) {
      return get(item, node.getRight());
    }else {
      //found it!
      return node.getData();
    }
  }

Try it out

• Given the following tree, show the steps needed to search for the value 12

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

Finding the min/max element

• Minimum and maximum values can be found recursively selecting the left subtree or recursively selecting the right subtree

  /** Returns the greatest value (right-most node) of the given subtree. */
  private E findMax(TreeNode<E> n) {
    if (n == null) {
      return null; //error case: no tree
    }else if (n.getRight() == null) {
      //can't go right any more, so this is max value
      return n.getData();
    }else {
      return findMax(n.getRight());
    }
  }

BST Insertions

• If tree is empty, value becomes root
• Compare value to current node starting at the root.
• If value is less than current node, recursively compare on left subbtree, otherwise if the value is greater than the current node, recursively compare on right subtree
• When recursive method attempts to recurse on left or right subtree, but that subtree is null, then new node is inserted at the position with the value

public void add(E item) {
  this.root = add(item, root);
  this.size++;
}

private TreeNode<E> add(E item, TreeNode<E> subtree) {
  if (subtree == null) {
    return new TreeNode<E>(item);
  }else {
    if (item.compareTo(subtree.getData()) <= 0) {
      subtree.setLeft(add(item, subtree.getLeft()));
    }else {
      subtree.setRight(add(item, subtree.getRight()));
    }
    return subtree;
  }
}

Try it out

• Create a binary search tree from the following values: 7, 4, 5, 6, 2, 9, 10, 8, 3, 1
• Create a binary search tree from the following values: 1, 2, 3, 4, 5, 6, 7

BST Removals

• Removing an item depends on three different cases

Removing a leaf node

• Simply remove the node

Removing a node with a single child

• Remove node and replace with child node

Removing a node with two children

• Remove node and replace with either in-order predecessor or in-order successor
• In-order predecessor is the left subtree's rightmost node
• In-order successor is the right subtree's leftmost node

 /**
   * Removes the first equivalent item found in the tree.
   * If item does not exist to be removed, throws IllegalArgumentException().
   */
  public void remove(E item) {
    this.root = remove(item, this.root);
  }

  private TreeNode<E> remove(E item, TreeNode<E> node) {
    if (node == null) {
      //didn't find item
      throw new IllegalArgumentException(item + " not found in tree.");
    }else if (item.compareTo(node.getData()) < 0) {
      //go to left, saving resulting changes made to left tree
      node.setLeft(remove(item, node.getLeft()));
      return node;
    }else if (item.compareTo(node.getData()) > 0) {
      //go to right, saving any resulting changes
      node.setRight(remove(item, node.getRight()));
      return node;
    }else {
      //found node to be removed!
      if (node.getLeft() == null && node.getRight() == null) {
        //leaf node
        return null;
      }else if (node.getRight() == null) {
        //has only a left child
        return node.getLeft();
      }else if (node.getLeft() == null) {
        //has only a right child
        return node.getRight();
      }else {
        //two children, so replace the contents of this node with max of left tree
        E max = findMax(node.getLeft());  //get max value
        node.setLeft(remove(max, node.getLeft())); //and remove its node from tree
        node.setData(max);
        return node;
      }
    }
  }

Try it out

Using the following tree:

         5
        / \
       2   8
      / \   \
     1   3   15
            /  \
           13  22
          /
         12    

• Show what the tree looks like after removing 12
• After removing 12, show what the tree looks like after removing 22
• After removing 22, show what the tree looks like after removing 15
• Show what the tree looks like after removing the root node