Binary Trees


A binary tree is either:
    1.  An empty tree; or
    2.  a node, called a root (the node contains the data), and two children, left and right, each of which are themselves binary trees.   (Berman, "Data Structures via C++:Objects by Evolution", 1997.)

We are defining a BinaryTree class as a wrapper around a TreeNode object, called a root (each TreeNode object contains the data and two children, left and right, each of which are themselves TreeNode objects).  

Mini Lab

Looking at the Code

In class you will have discussed some of the methods and properties that a BinaryTree class might contain.  You should also be familiar with the concept of tree traversal methods.  Today you will implement client code to construct a tree, and you will implement several traversals.
  1. Download the Trees.zip file and create a project for it.
  2. Look at the instance variables and constructor of the binary tree class provided to figure out how this implementation represents empty trees, leaves, and non-leaf root nodes.
Think about your constructor.  Our definition talks about empty trees.  We can create a tree that is entirely empty.  What properties does an empty tree have?
  1. Look at the constructor provided.  Does it match your expectations?
  2. Construct an empty tree in the main method in the BinaryTreeLab class.

Breadth-First Insertion

What other methods are provided in the code ?

  1. Look at the rest of the code, and determine how to add elements to a tree in breadth-first (top-down, left-to-right) order.  What does it mean to add in breadth-first order?
  2. Modify the main method to insert the values 12, 7, 3, 4, 8, 25, 0, 142, 17, and 26 in your tree.  Since the tree expects objects rather than int primitives, you will need to use the Integer class.

Visitors

Find the method in the BinaryTree class for doing a breadth-first traversal.  Notice that it takes a single parameter, which is a NodeVisitor object.  Actually, NodeVisitor is an interface that specifies a single method, the visit method.  The visit method also takes a single parameter, which is a node in a binary tree.  Basically, a traversal consists of stepping through all the nodes in a tree in a particular order, and calling the visit method of a particular NodeVisitor object for each node.  This allows us to write generic traversal algorithms that can do a number of different activities.  For example, we might have one NodeVisitor object that prints each node (see the PrintAction class), another than sums up numeric values in each node, and another than finds the minimum or maximum node value.  Each of these tasks requires traversing the tree, but we don't need to write a separate traversal algorithm for each activity.  Instead, we write traversal algorithms for each traversal ordering, and pass to each one an appropriate NodeVisitor object.  The NodeVisitor is responsible for taking the appropriate action.

  1. Test your program by printing the values in the tree in breadth-first order. Note which NodeVisitor class gets passed to the traversal algorithm to print values.  (The code to do this is already in the main method, but is commented out.)
  2. Implement a new class, similar to the PrintAction class, that implements the NodeVisitor interface. Your new class should assume that the data elements in the binary tree nodes are Integer objects (as they are in this case) and sum them up.  Your class should keep track of the sum as an int instance variable and, in the visit method, should add the integer value of the data parameter to the sum, so long as the data parameter is not null.  To do this, you will need to cast the parameter to an Integer and then use the intValue method.  (Document the precondition that the parameter must be an Integer.)  Provide an additional method that you can call from the main after the traversal is complete, which will return the computed sum.  Test your new class by using it in a traversal and then asking for the sum.

Recursive Depth-First Traversals

How else might you traverse the tree?  Remember that, in addition to the breadth-first traversal algorithm, there are three ways to traverse a tree using depth-first traversal algorithms.

Because of the recursive nature of the binary tree structure (trees are sometimes referred to as recursive data structures), the depth-first traversals can be implemented with recursion.

Here is the algorithm for traversing a tree using a pre-order traversal:
    if the tree is not empty,
        visit the root
        recursively do a pre-order traversal of the left subtree
        recursively do a pre-order traversal of the right subtree

Question: What is the base case for this recursive algorithm?

  1. Implement the algorithm above for a pre-order traversal.  Test your method using the PrintAction visitor and your new summing visitor.  Are the results the same or different from your previous results with the breadth-first traversal?  Are the results what you expected?
  2. Implement a method that performs an in-order traversal.
  3. Implement a method that performs a post-order traversal.

Additional Methods

Implement the following methods using recursion.  Most will follow the typical depth-first recursive algorithm, but with more explicit handling of the base case than the traversal algorithms above.  Some may need to handle more than one base case, such as both empty trees and leaves.  The algorithm below is an example of pre-order handling, but a different order may be appropriate for some methods.
    if the tree is empty,
        handle this base case
    otherwise,
        do something with the root
        recursively call this method for the left subtree, possibly doing something with the return value
        recursively call this method for the right subtree, possibly doing something with the return value

  1. isLeaf -- returns true if the node is a leaf node; false otherwise
  2. numNodes -- returns the number of nodes in the tree
  3. numLeaves -- returns the number of leaves (nodes with no children) in the tree
  4. depth -- returns the depth (or height) of the tree
  5. contains -- takes an Object as a parameter and returns true if the object is in the tree; false otherwise
  6. numOccurrences -- takes an Object as a parameter and returns the number of occurrences of the object in the tree
  7. equals -- takes an Object as a parameter and returns true if it is a BinaryTree and is equal to this binary tree; two binary trees are equal if they contain the same nodes (and the same number of each node), although the order of the nodes and the shape of the trees may differ  (NOTE: whenever you redefine the equals method, you should also redefine the hashCode method; in this case, you may redefine it to throw an UnsupportedMethodException.)

    Hint: Here's an approach you might try.  Create a recursive helper method that returns true if two trees passed to it as parameters both have the same number of occurrences of all the values in this tree.  The recursive calls would step through the subtrees of this tree as usual, but would continue to pass the same two trees as parameters (see the example below, which looks worse than it really is).  The structure of the recursive helper method would be very similar to your other recursive methods.  The equals method, though, would simply call the helper method, passing itself and the other tree as the two parameters.

    Example: Let variables a and b be binary trees (a) and (b) in Figure 8.1 on p. 279 (which we can see are equal).  Consider the expression a.equals(b).  The equals method would call the recursive helper, passing it trees a and b as actual parameters.  Assume that the formal parameter names for the two trees in the recursive helper method are t1 and t2.  (So, t1 is tree (a) and t2 is tree (b).)  The recursive helper method would verify that trees t1 and t2 have the same number of occurrences of the root value in this tree (A) and the same number of occurrences of all values in the left and right subtrees of this tree.  The recursive call to the left subtree would verify that trees t1 and t2 (which are still trees (a) and (b)) have the same number of occurrences of the root value in this subtree (B) and the same number of occurrences of all values in the left and right subtrees of this tree.  Those subtrees are empty, so the recursive call can just return true when called for them.  (Equal trees do not need to contain the same number of empty "dummy" subtrees.)  Similarly, the recursive call to the right subtree of the original tree would verify that trees t1 and t2 have the same number of occurrences of the root value in that subtree (C) and the same number of occurrences of all values in the (empty) left and right subtrees of that tree.

Another Visitor

Another useful method for a binary tree would be a method that calculated the maximum or minimum value in the tree.  We can calculate these values from outside the BinaryTree class, however, by implementing a new NodeVisitor.

  1. Implement a new NodeVisitor class called ExtremeValueCalculator to find the extreme values (minimum and maximum) in a tree.  The ExtremeValueCalculator class should have two Comparable instance variables, representing the largest and smallest values seen so far.  In the visit method, if the data parameter is null, do nothing.  If it is not null, then cast it to a Comparable and test it against the smallest and largest values seen so far.  (Document the precondition that the parameter must be Comparable.)  If either of the instance variables are null, or if the parameter is smaller than the smallest value or larger than the largest value seen so far, then set the appropriate instance variable to the parameter.  (Could the parameter become both the smallest and the largest value seen so far?  Be sure to handle this case.)  Provide additional methods that you can call from the main after the traversal is complete, one of which will return the minimum value and one of which will return the maximum value (both Comparable).  Test your new class by using it in a traversal and then asking for the minimum and maximum values.

Another Depth-First Method

Implement the equals method.  This method takes an Object as a parameter and returns true if it is a BinaryTree and is equal to this binary tree.  We will define two binary trees as equal if they contain the same nodes (and the same number of each node), although the order of the nodes and the shape of the trees may differ.  (NOTE: another definition of equals could insist that the two binary trees have the same nodes in the same locations in the tree.)

Whenever you redefine the equals method, you should also redefine the hashCode method; in this case, you may redefine it to throw an UnsupportedMethodException.

Hint: Here's an approach you might try.  Create a recursive helper method that returns true if two trees passed to it as parameters both have the same number of occurrences of all the values in this tree.  The recursive calls would step through the subtrees of this tree as usual, but would continue to pass the same two trees as parameters (see the example below, which looks worse than it really is).  The structure of the recursive helper method would be very similar to your other recursive methods.  The equals method, though, would simply call the helper method, passing itself and the other tree as the two parameters.

Example: Let variables a and b be binary trees (a) and (b) in Figure 8.1 on p. 279 (which we can see are equal).  Consider the expression a.equals(b).  The equals method would call the recursive helper, passing it trees a and b as actual parameters.  Assume that the formal parameter names for the two trees in the recursive helper method are t1 and t2.  (So, t1 is tree (a) and t2 is tree (b).)  The recursive helper method would verify that trees t1 and t2 have the same number of occurrences of the root value in this tree (A) and the same number of occurrences of all values in the left and right subtrees of this tree.  The recursive call to the left subtree would verify that trees t1 and t2 (which are still trees (a) and (b)) have the same number of occurrences of the root value in this subtree (B) and the same number of occurrences of all values in the left and right subtrees of this tree.  Those subtrees are empty, so the recursive call can just return true when called for them.  (Equal trees do not need to contain the same number of empty "dummy" subtrees.)  Similarly, the recursive call to the right subtree of the original tree would verify that trees t1 and t2 have the same number of occurrences of the root value in that subtree (C) and the same number of occurrences of all values in the (empty) left and right subtrees of that tree.

Authors: Autumn C. Spaulding autumn@max.cs.kzoo.edu
and Alyce Brady abrady@kzoo.edu