Trees

Goals

Concepts

Library

Lesson

A tree is directed graph in which each vertex (usually referred to just as a “node”) has at most one edge coming in, and may have any number of edges going out; to vertices that are not shared with other vertices. A traditional file system is a well-known example of a tree, in which each directory can itself contain files and subdirectories, and so on. A Java class hierarchy is also a tree, as you can see in the Vehicle class diagram from a previous lesson.

Vehicle hierarchy class diagram.
Vehicle hierarchy class diagram.

A tree has certain features that are given names:

Binary Tree

As you might have guessed from the terms above, a tree is a good data structure for representing the relationship among objects. A tree can hold objects in a sorted order. A simple-to-understand example of such a tree is a binary tree, in which each node has potentially two children—hence the use of the term “binary”. The two child nodes are called the “left” and “right” nodes, for obvious reasons. Here is an example binary tree node holding java.util.Long instances:

Example BinaryTreeNode implementation.

public class BinaryTreeNode {

  private final Long value;

  /** @return The value represented by this node. */
  public @Nonnull Long getValue() {
    return value;
  }

  private BinaryTreeNode left = null;

  /** @return The left child node, or <code>null</code> if there is no left child node. */
  public @Nullable BinaryTreeNode getLeft() {
    return left;
  }

  /**
   * Sets the left child node.
   * @param left The left child node, or <code>null</code> if there is no left child node.
   */
  public void setLeft(@Nullable final BinaryTreeNode left) {
    this.left = left;
  }

  private BinaryTreeNode right = null;

  /** @return The right child node, or <code>null</code> if there is no right child node. */
  public @Nullable BinaryTreeNode getRight() {
    return right;
  }

  /*
   * Sets the right child node.
   * @param right The right child node, or <code>null</code> if there is no right child node.
   */
  public void setRight(@Nullable final BinaryTreeNode right) {
    this.right = right;
  }

  /*
   * Creates a node containing an object.
   * @param value The object to store in the node.
   */
  public BinaryTreeNode(@Nonnull final Long value) {
    this.value = checkNotNull(value);
  }

}

You can use a binary tree to hold sorted numbers. For each node, use the subtree tree on the left to hold numbers less than the number held by the node itself, and use the tree on the right would hold numbers greater than the node itself, as in the diagram.

Binary search tree.
Binary search tree.

This sort of tree makes it easy to search for items. Instead of searching through every single value, if the value held by a particular node does not match one needs either to search the left subtree or the right subtree, based upon whether the object being searched for is less than or greater than the object held by the node. You should see that this sort of binary tree represents the pattern of searching that would occur in the binary search algorithm you already learned. Not coincidentally this type of binary tree is called a binary search tree (BST).

Example BinarySearchTree implementation.
public class BinarySearchTree {

  private BinaryTreeNode rootNode = null;

  //TODO add methods to allow adding values to the tree

  /**
   * Determines if the given value is contained in the tree.
   * @param value The value to check for.
   * @return true if the value is contained in the tree.
   */
  public boolean contains(@Nonnull final Long value) {
    if(rootNode == null) {
      return false;  //the tree is empty
    }
    return contains(rootNode, value);  //search the BST recursively from the root node
  }

  /**
   * Recursively searches to determine if the given value is contained in the subtree
   * represented by the given node.
   * @param node The root node of the subtree to search.
   * @param value The value to check for.
   * @return true if the value is contained in the subtree.
   */
  protected static boolean contains(@Nonnull final BinaryTreeNode node, @Nonnull final Long value) {
    if(value.longValue() == node.getValue().longValue()) {  //if this node has the value, we've found it
      return true;
    } else if(value.longValue() < node.getValue().longValue()) {  //our value is less than the node value
      if(node.getLeft() != null) {  //search the left branch if there is one
        return contains(node.getLeft(), value);
      }
    } else if(value.longValue() > node.getValue().longValue()) {  //our value is greater than the node value
      if(node.getRight() != null) {  //search the right branch if there is one
        return contains(node.getRight(), value);
      }
    } else {
      throw new AssertionError("A number should be less than, equal to, "+
          "or greater than another number; we made a mistake somewhere.");
    }
    return false;  //this value cannot be in the BST
  }

}

Tree Traversal

For a student leaving school on foot, there may be several ways to get home. They will cross the same streets on the way, but they will cross them in a different order depending on which corner they turn. Similarly it is possible to traverse a tree in several ways, and they result in different orders in which the nodes are visited.

Depth-First Traversal

One group of traversal methods is called depth-first traversal: for each child node, look at all of its child nodes before going on to the next child node. There are three ways this can be done, based upon whether the children of each child node are visited before the child node itself: pre-order traversal, in-order traversal, and post-order traversal. This is best explained by diagrams in the following table.

Pre-Order Traversal In-Order Traversal Post-Order Traversal
Binary tree depth-first pre-order traversal. Binary tree depth-first in-order traversal. Binary tree depth-first post-order traversal.
F, B, A, D, C, E, G, I, H A, B, C, D, E, F, G, H, I A, C, E, D, B, H, I, G, F

Breadth-First Traversal

The other general class of tree traversal is breadth-first traversal, in which all the nodes at each level are visited before any of children are visited.

Breadth-First Traversal
Binary tree breadth-first traversal.
F, B, G, A, D, I, C, E, H

Review

In the Real World

Self Evaluation

Task

Create your own implementation of a binary search tree, implementing the following interface, complete with unit tests. For books with a range of publication dates, use the starting date of the range as the publication date. You may have to update your publication interface so that it returns some publication date for all publication types.

/** A binary search tree for publications that sorts by publication date. */
public interface PublicationBinarySearchTree {

  /**
   * Adds a publication to the BST.
   * The publication will be sorted in the tree based upon its publication date.
   * If a publication is already in the tree with the same publication date,
   * no publication is added.
   * @param The publication to add.
   */
  void add(@Nonnull Publication publication);

  /**
   * Determines if a publication is contained in the tree
   * with the publication date as the one given.
   * @param publication The publication the date of which to search for.
   * @return <code>true</code> if a publication is contained in the tree with the same publication date.
   */
  boolean contains(@Nonnull Publication publication);

  /**
   * Prints all publications in the tree using depth-first in-order traversal.
   * @implSpec This implementation uses the {@link Publication#toString()} method of each object in the tree.
   * @deprecated This method is for learning and will be removed in the future.
   */
  @Deprecated
  void printAll();

}

After adding all your publication to a PublicationBinarySearchTree (in no particular order) from the Booker application, call the PublicationBinarySearchTree.printAll() method to print out each publication in order of publication date.

Lastly, remove the getFirstNode() method from your LinkedList interface, which you added as a learning tool in a previous lesson. Your Booker application can still use the LinkedList.get(int index) and LinkedList.getLength() methods to iterate through the lists. As you might guess, retrieving objects from the middle of a linked list using index-based lookup is not very efficient, but you will learn a better approach for iterating through the elements in a linked list.

See Also

References

Acknowledgments