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.)

Mini Lab

Looking at the Code

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.

3. What properties does an empty tree have?
   
4. Look at the constructor provided.  Does it match your expectations?
   
5. 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 that 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

Analysis Questions: Inside or Outside?

The breadth-first add method and breadthFirstTraversal method have almost the same algorithm.  Note, though, that while the add method uses instance variables directly, the breadthFirstTraversal method makes use of accessor methods. 

1. Could the add method have been implemented using method invocations rather than accessing instance variables directly?  Could the breadthFirstTraversal method have been implemented using instance variables?
   
2. Could the breadthFirstTraversal method have been implemented outside the BinaryTree class as client code?  If so, would anything about the code have to change?  Try implementing a version of the breadthFirstTraversal method as a static method in the BinaryTreeLab class.  (Why would it have to be static?)
   
3. What are the benefits to having traversals within the class?  What about outside the class?  From a design standpoint, which do you think is better?  What about implementing other methods outside the class, such as numNodes or depth?  Justify your answers.

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 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 UnsupportedOperationException.

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