Binary Trees MINI-LAB

By Autumn C. Spaulding with Alyce Brady

Implementing a Binary Tree

A recursive definition of a binary tree is that it is either:

• An empty tree; or
• A node, called a root, containing the data and two children, left and right, each of which is itself a binary tree.

Looking at the Code

In preparation for this lab, you should be familiar with the general methods and properties of binary trees. You should also be familiar with the concept of tree traversal methods. In this lab you will implement client code to construct a tree, and you will implement several traversals.

• Download six files into a new Trees folder:
  • K_BinaryTree.java
    (The Binary Tree interface.)
  • K_AbstRecBinTree.java
    (An abstract class that defines the structure of a recursive binary tree, along with some methods. It does not define the add and remove methods, leaving them abstract.)
  • K_CompleteRecBinTree.java
    (A subclass of the abstract class that defines the methods to add and remove elements from the tree in a way that preserves it as a Complete Binary Tree.)
  • BinaryTreeLab.java
    (A test driver, containing the main method and a number of tests.)
  • NodeVisitor.java
    (described later)
  • PrintAction.java
    (described later)
• Look over the K_BinaryTree interface to see which methods are specified.
• Look at the instance variables, constructor(s), and basic observer methods (isEmpty, getElement, leftChild, and rightChild) of the K_AbstRecBinTree class to figure out how this implementation represents empty trees, leaves, and non-leaf root nodes.
• Look over the K_CompleteRecBinTree class. What instance variables, constructor(s), or methods does it have? Is that what you expected?
• How many constructors do these classes have? Is that what you expected? Can we construct empty trees and trees with internal nodes and leaf nodes with the methods provided, or do we need additional methods for basic tree construction?

Initial Experimentation

Read the code

• Copy your queue interface and class, along with the linked list classes used by your queue implementation, into your Trees folder.
• Look over the K_AbstRecBinTree and K_CompleteRecBinTree classes and the BinaryTreeLab test driver. What do you expect will be the result if you run the driver without modification?
  Tip: Always explicitly identify expected results before running a test. If it is complicated, write your expected results down. Otherwise it is too easy to see actual results and say, "Yeah, that looks right," even if the results are close but wrong.
• Note that the test driver add values (12, 7, 3, etc.) to the tree. What tree do you expect this to construct? Draw it out. What should be the result of a pre-order traversal? A breadth-first traversal?
  The tree expects Integer objects rather than int values, but Java "auto-boxing" will turn int values into Integer objects automatically, when needed.

Run the code

• Compile and run the BinaryTreeLab program as provided. Did it behave as expected? If not, study the code further to understand why not. Was the problem with the actual results, or with your expected results? Study the code to understand any differences in behavior.
• How much of the K_AbstRecBinTree and K_CompleteRecBinTree classes can you test with the methods you have so far? What more would you need to test it more thoroughly?

Visitors

Find the method in the K_AbstRecBinTree class for doing a pre-order depth-first traversal. Notice that it takes a single NodeVisitor parameter. 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. A traversal could consist 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 responsible for executing the appropriate action.

• Read over the NodeVisitor interface and the PrintAction class. Do you see how this could result in printing all of the data elements in the tree if the visit mathod in the PrintAction class were called for each node in the tree?

Recursive Depth-First Traversals

Remember that, in addition to breadth-first traversals, there are three depth-first ways to traverse a tree.

Because of the recursive nature of the binary tree structure, 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,
        view or do something with the root (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?

• Implement the preOrderTraversal method in K_AbstRecBinTree using the algorithm above for a pre-order traversal.
• Note that the BinaryTreeLab class was already calling the stub version of this method before you completed it, passing it a PrintAction visitor object. How do you expect the program to behave now? Be explicit about exactly what you expect the results to be. Run the program. Did the actual results match your expected results? If they did not match, was the problem with the actual results, or with your expected results? Study the code to understand any differences in behavior.
• Implement the inOrderTraversal method. Modify the main method to test your completed method. Are the results the same or different from your previous results with the pre-order traversal? Are the results what you expected?
• Implement the postOrderTraversal method, modify the main method to test it, and run your program. Are the results what you expected?

Breadth-First Traversal

• Read over the add method in K_CompleteRecBinTree to see how it adds elements in breadth-first order.
• Implement the breadthFirstTraversal method in K_AbstRecBinTree using a queue and a loop similar to that in the add method in K_CompleteRecBinTree. (The breadthFirstTraversal method is simpler, though.) Modify the main method to test your completed method. Are the results what you expected?

Additional Methods

Add signatures for the following methods to the K_BinaryTree interface and then implement them in K_AbstRecBinTree. Most of these methods will follow a 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 existing height method in K_AbstRecBinTree is similar to a post-order traversal, while the algorithm below is an example of pre-order handling. 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

• isLeaf() Returns true if the node is a leaf node; false otherwise. (This method is not recursive, but could be used by other recursive methods.)
• numNodes() Returns the number of nodes in the tree.
• numLeaves() Returns the number of leaves (nodes with no non-empty children) in the tree.
• contains(T item) Takes an object as a parameter and returns true if the object is in the tree; false otherwise.
• numOccurrences(T item) Takes an object as a parameter and returns the number of occurrences of the object in the tree.

Other Visitors

We can add new functionality to the program without having to modify the K_AbstRecBinTree class if the behavior is just based on the data values in the tree and not their relationships to each other. We can do this by creating new Visitor classes.

• Implement a new class (name it SumReduction), similar to the PrintAction class, that implements the NodeVisitor interface. Note that this class specifies that the data elements in the binary tree nodes are Integer objects. Your class should sum the data elements in the visit method, keeping track of the sum as an int instance variable. (The method should never be called with a null data parameter, but it is still a good idea to check for that before adding the value to the sum.) Your new class should also have an additional method that returns the sum. Modify the main to test your ability to calculate and then print the sum.
• Another useful method for a binary tree would be a method that calculated the maximum or minimum value in the tree. 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.

Submit your completed program through Kit, under Binary Tree.

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!