CS 261 Lab I - Binary Tree Properties

Due Wed Apr 02 at 9:00am

Overview

In this lab you will practice working with Binary Trees in order to solidify your understanding of this data structure. You will be working with the node-based version of a BinaryTree that we discussed in class, but you will be extending this class to add new functionality that describes the structure of the tree.

This lab will be completed in pairs. Remember to review the pair programming guidelines before you get started!

Objectives

To practice implementing methods for with binary trees
To learn about further "properties" of tree data structures

Necessary Files

You will need to download the copy of the BinaryTreeLab.zip file. This file contains a copy of the BinaryTree<E> class that we implemented in class (possibly with a few tweaks). You will need to import this class into Eclipse.

Assignment Details

This lab is pretty straight-forward, but you should still be sure to read the whole assignment carefully!
You will be creating a new class AnalyzableBinaryTree (yes it is a long name, but it describes what you're doing!) that extends the existing BinaryTree class. Remember to make your new class generic!
- You will need to create new constuctors for your AnalyzableBinaryTree. You should include equivalent versions of each of the constructors in the parent class. These constructors can just call their parent's version of the constructor using super().
- Remember that as a subclass, you have inherited all of your parent's instance variables (and inner classes)--you do not need to make your own copies of them!
Your AnalyzableBinaryTree will include the following new methods (these are listed in suggested order of completion):
1. public AnalyzableBinaryTree<E> attachLeft(E data)
  This method will help you construct Binary Trees for testing by letting you easily add data. This method should attempt to add a new Node with the given data to the the left branch of the tree. If the left branch of the tree is already occupied, your method should throw an IllegalStateException (be sure and pass the Exception a message about what went wrong!). You should then return a new AnalyzableBinaryTree that represents the subtree rooted by the Node you just added!
  - Remember that you can call this method on subtrees in order to add elements anywhere in your "full tree"
  - It's easy to return the new subtree--just call the appropriate constructor (similar to what the getLeftSubTree() method in the parent class does!)
  - Note that returning the new tree it becomes possible to chain together attachment calls. Thus code such as tree.attachLeft(2).attachLeft(6).attachLeft(1) will create a tree with the nodes 2 - 6 - 1 going down the left side.
2. public AnalyzableBinaryTree<E> attachRight(E data)
  This method will work exactly the same as the previous, except that you will be attaching the new data to the right branch, rather than the left. Again, if throw an IllegalStateException if the right branch is already occupied!
3. public int size()
  This method should compute and return the number of Nodes in the tree. Use recursion!
4. public int getHeight()
  This method should compute and return the height of the tree (the distance from the root to the furthest away leaf). This method is a lot like calculating the size. Think about the "base case" of your recursion, and how you can build off of that!
5. boolean isFull()
  This method should return whether or not the tree is full (that is, whether or not ever node is either a leaf or has exactly two children; see pg302 of the textbook for an example). Again, recursion should make this pretty straight forward.
  - HINT: You might get good mileage out of a helper method that counts the number of children a node has, so you can determine if a node has 0, 1 or 2 kids.
6. boolean isPerfect()
  This method should return whether or not the tree is perfect. A perfect tree is a full tree in which all of the leaves are on the bottom level (and thus every node not on the bottom level has 2 children). This means that a perfect tree of height h has exactly 2^h-1 nodes (again, see page 302 of the text for an example). If you use this fact and your previous methods, this method should be easy to write.
7. boolean isComplete()
  This method should return whether or not the tree is complete. A complete tree is one in which all levels except the last are completely filled (i.e., perfect), and any nodes missing are to the right of their siblings/cousins (once again, see page 302 of the textbook).
  - This method is one of the more complex to write. You can solve it recursively, but you might also consider doing a breadth-first traversal (using a queue). Start by enqueuing the root. Then you can count nodes by dequeue one node, counting it, and enqueuing its children (left then right). Stop as soon as you dequeue a null node--this means you should have finished counting every node in the tree (because there is now no one to the right of you!). If you have counted every node (determined by the size of the tree), then you have a complete tree.
    - You can use the Queue class that we implemented in lecture, or you can just use a LinkedList, with the addLast() method acting as push and the removeFirst() method acting as pop.
Remember that your methods should have the above signatures: use them as launchers with private recursive helper methods!
If you get stuck, be sure to ask for help!

Testing your Class

You should create an submit a Tester that demonstrates that your methods work. This is a good plan anyway, but it'll help us to see what you've done.

Remember to test more than one tree! You can construct these trees using the nested constructors we used in class, or by using your attachLeft and attachRight methods.
A good note for testing boolean "isSomething" methods--be sure and test it with an input that you expect to return true AND an input that you expect to return false. So test "isFull" with both a full BinaryTree and a not-full BinaryTree.
Test with trees with a height greater than 2 or 3--this will make sure there are no "one time recursing works" flukes. Remember: the goal is to try and break your own code!
Be sure and test edge cases as well: what happens when you call these methods on an empty tree? A tree with a single node? A degenerate tree? A tree with a lot of nodes?

Extensions

There are plenty of extra analytical functionality you might add. Informative methods can be worth up to 5 extra credit points. Some examples:

An isDegenerate() method that reports whether or not each node has either 0 or 1 children (and thus the tree is really just a linked list).
An isBalanced() method that reports whether or not the height of the two subtrees of any node differens by at most 1 level.
As a bonus, try overriding the .equals() method so that it returns true when two trees have equal data in the same structure.

Submitting

Make sure your name is in a class comment at the top of both your AnalyzableBinaryTree and your Tester, and upload them to the LabI submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

After you have submitted your solution, log onto Moodle and submit the Lab I Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded based on approximately the following criteria:

You have extended the BinaryTree class with appropriate constructors [6%]
Working attachLeft() and attachRight() methods (which throw appropriate exceptions) [15%]
Working size() method [11%]
Working getHeight() method [11%]
Working isFull() method [11%]
Working isPerfect() method [11%]
Working isComplete() method [15%]
A Tester that demonstrates the functionality of all your methods [15%]
You completed your lab partner evaluation [5%]