MyTreeNode Properties

Trees and Recursion!

Now that we have the basic structure of our MyTreeNode<T> class, we can begin implementing methods that use recursion to calculate useful properties of the tree nodes. In each of the following, it might be useful to first think about:

  1. What is the base case of the problem? When do we know the answer without having to recurse?
  2. How can we make the problem smaller, and how do we use the same function on that smaller problem?
  3. How do we create the total solution by chaining together the returns? How do we use the value returned by the recursive call as part of the return of this function call?

Root and Leaves

To help us with our recursive properties below, we will create a couple public functions that determine the type of a node.

First, implement a public method called isLeaf that returns true if the node is a leaf and false otherwise. Looking at the children instance variable should help here.

Second, implement a public method called isRoot that returns true if the node is the root of the tree and false otherwise. Looking at the parent instance variable should help here.

Before moving on, create a couple unit tests verifying that both the isLeaf and isRoot methods are implemented properly.

Tree Node Size

As a first recursive property, implement a public method called size that returns the size of a MyTreeNode<T>. Recall that the size of a node is its number of descendents (itself, its children, its children’s children, etc.). This method should have no parameters.

Then, in your MyTreeNodeTest.java file, create a unit test that verifies the correctness of your size method. You can think about adding children to different parts of the tree, then checking that the value returned by size is correct for each node.

Tree Node Depth

As a second recursive property, implement a public method called depth that returns the depth of a MyTreeNode<T>. Recall that the depth of a node is the number of branches from the root node to that node. So the root node has a depth of 0, its children have a depth of 1, their children have a depth of 2, etc. This method should have no parameters.

Then, in your MyTreeNodeTest.java file, create a unit test that verifies the correctness of your depth method. You can think about adding children to different parts of the tree (as you did in your size test), then checking that the value returned by depth is correct for each node.

Tree Node Height

As a third recursive property, implement a public method called height that returns the height of a MyTreeNode<T>. Recall that the height of a node is the number of branches from itself to its deepest descendent leaf. This method should have no parameters.

Then, in your MyTreeNodeTest.java file, create a unit test that verifies the correctness of your height method. You can think about adding children to different parts of the tree (as you did in your size and depth tests), then checking that the value returned by height is correct for each node.

Tree Node Contains

As a final recursive property, implement a public method called contains that returns true if a given item of type T is stored in one of the descendents of a node (including the node itself), else it returns false. As a friendly reminder, you probably want to use the equals method to check if the given item is equal to the item instance variable of a tree node:

this.item.equals(item);

Then, in your MyTreeNodeTest.java file, create a unit test that verifies the correctness of your contains method. You can think about adding children to different parts of the tree, then checking whether the contains method called on the root node returns the correct value for items that are and are not stored in its descendent nodes.

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.