Lab 14: Trees

## A. Intro

Download files for lab 14 and make a new Eclipse project out of them.

In earlier labs, we were discussing and implementing different variants of Linked Lists. In this lab and the next few, we will talk about a data structure called a tree. The meaning of the tree data structure originates from the notion of a tree in real life.

Below is a conceptual visualization of a tree. It's not really a box and pointer diagram and should not be interpreted as a literal implementation in Java.

Note that while a tree in real life starts small at the bottom and branches out upwards, trees in computer science are typically drawn such that they start small at the top and branch out downwards.

#### Some Vocabulary

Below is some useful terminology.

Term Description
Node Single element in a tree
Edge A connection between two nodes
Path A series of one or more edges that connects two nodes
Leaf A node with no children.
Root The topmost node, which does not have a parent.

In our example, if we consider each box as a node, then 1, 2, 3, 4, 5, 6, and 7 are all nodes. There is a direct edge from 1 to 2. There is no direct edge from 1 to 7, but there is a path from 1 to 7, which consists of edges 1 -> 3 and 3 -> 7. 1 is the root node. 4, 5, and 7 are all leaf nodes.

#### Relationships

These terms are defined in relationship to a particular node. In other words, they only make sense when defined with respect to a particular current node.

Term Description
Child Below the current node.
Parent Singular node connected directly above the current node.
Sibling Nodes with the same parent.
Ancestor All nodes on the path from the selected node up to and including the root
Descendant All the children, children's children, and so forth of a node.
Subtree The tree consisting of the node and all of its descendants
Height The length of the path from the node to its deepest descendant. By length, we mean the number of nodes traveled along a given path. Therefore, the height of a leaf node is 1. Some people would alternatively define height as the number of edges traversed, and the height of a leaf would be 0.
Depth The length of the path from the node to the root.

We can also define the height of a tree and the depth of a tree, and it is usually assumed that this refers to the height of the root node and the depth of the deepest leaves respectively.

#### Definition

For a linked structure to be considered a tree, no node can be a direct child of multiple nodes. Further, there can be no cycles in the nodes, that is, paths that start at and return to the same node. Finally, all nodes must be a descendent of the root (except the root itself).

#### Discussion: Examples of Trees

Discuss with your partner whether the following examples would be considered trees as we've introduced them. Then add a post to the discussion.

• Family Tree
• Amoeba Family Tree (instead of a man and a woman creating any number of children, we have a single entity that creates any number of children)

## B. Amoeba Family Tree

An amoeba family tree is an example of our above definition of a tree. It is simpler than a normal family tree because amoebas do not get married. An amoeba has one parent, many (zero or more) siblings, and many (zero or more) children. An amoeba also has a name.

Below is the skeleton code for an Amoeba. The full code is located at `lab14/AmoebaFamily.java`.

``````class Amoeba {
String myName;
Amoeba myParent;
ArrayList<Amoeba> myChildren;
}``````

And below is a box and pointer diagram.

Amoebas (or amoebae) live dull lives. All they do is reproduce. So all we need to keep track of them are the following methods:

``````// A constructor that starts an Amoeba family with an amoeba with the given name.
public AmoebaFamily(String name);

// Add a new amoeba named childName as the youngest child of the amoeba named parentName.
// Precondition: the amoeba family contains an amoeba named parentName.
public void addChild(String parentName, String childName);

// Print the amoeba family tree.
public void print(); ``````

#### Void Recursive Methods

In the `AmoebaFamily` class we provided the method `addChild` to add a new Amoeba to the `AmoebaFamily` tree. The method implements a general traversal of the tree using a void recursive method. You are going to write three other traversals that use a void recursive method. Your goal is to make the solution to the three methods as similar as possible to `addChild`.

#### Exercise: Make All Names Lowercase

``````// Makes all Amoeba names only lower case letters.
public void makeNamesLowercase();``````

#### Exercise: Replace the Name of an Amoeba

``````// Replaces the name of an amoeba named currentName with the name newName.
// Precondition: the amoeba family contains exactly one amoeba named currentName.
public void replaceName(String currentName, String newName);``````

#### Exercise: Print the Names of All Amoebas in the Family.

``````// Print the names of all the amoebas in the family, one on each line
public void printFlat();``````

#### Exercise: Pretty Print

You're going to write a more interesting print method. It should print the root amoeba's name and the names of all its descendants. One name should be printed per line. The names of the children of each descendant Amoeba should be printed on the lines immediately following; they should be indented four spaces more than the name of their parent. Thus the output should appear in the form

``````amoeba_name
child_name
grandchild_name
great_grandchild_name
great_great_grandchild_name
grandchild_name
child_name
grandchild_name
child_name
child_name
grandchild_name``````

You will probably need a helper method whose argument keeps track of the indenting level, but the form should still be almost identical to addChild and the other three examples you worked with.

#### Non-void Recursive Methods

All of the methods we have written for the `AmoebaFamily` class have not returned anything! We will be able to do cooler things if we can return values. The next example will take advantage of this.

#### Longest Name

First, switch which partner is coding for this lab, if you haven't already.

We've provided the following method:

``````// returns the length of the longest name in the Amoeba Family
public int longestNameLength();``````

Your goal is to write a method `longestName` that is as similar to `longestNameLength` as possible. The goal is to try to identify the pattern in these non-void recursive methods. You will use the patterns here in the next two exercises.

``````// this method should return the name that is longest of all names in the tree.
public String longestName(); ``````

#### Amoeba Counting

Write and test an AmoebaFamily method named `size` that returns the number of amoebas in this family.

#### OPTIONAL: Finding the Busiest Amoeba

Consider an `AmoebaFamily` method named `busiest`, which returns the name of the amoeba with the most children.

If there are more than one amoeba with the same maximum number of children, you may return the name of any of them. If the tree is empty, return null.

Hint: The `longestName` method is a good model for `busiest`. Depending on your implementation, you may find that you need to keep track of two sets of information, but your helper method can only return one thing. Think flexibly and consider what you can return that will help keep track of those two sets of information.

#### Computing the Height

The height of a node in a tree is the maximum length of a downward path from that node to a leaf. For now, we'll define the height of a leaf as 1, and the height of a null tree as 0. Sometimes you'll see a different convention, defining the height of a leaf as 0, and the height of a null tree as -1.

The following code is an incorrect implementation of the `height` method. Discuss with your partner what the bug is.

``````//In Amoeba
private int height() {
if (myChildren.isEmpty()) {
return 1;
} else {
int bestSoFar = 1;
for (Amoeba a : myChildren) {
bestSoFar = 1 + Math.max(a.height(), bestSoFar);
}
return bestSoFar;
}
}``````

Then write a JUnit test that includes the case you identified and one other case. Then fix the implementation of the `height` method. This means include a `height` method in the `AmoebaFamily` class, similarly to all the other `AmoebaFamily` methods you've written so far.

## C. Binary Trees

As noted earlier, a common special case is a binary tree, one in which each node has at most two children. Rather than store the children in an `ArrayList` as was done in `Amoeba` nodes, one normally just has two separate variables `myLeft` and `myRight` for the left and right children.

Three processing sequences for nodes in a binary tree occur commonly enough to have names:

• preorder: process the root, process the left subtree (in preorder), process the right subtree (in preorder)
• postorder: process the left subtree (in postorder), process the right subtree (in postorder), process the root
• inorder: process the left subtree (in inorder), process the root, process the right subtree (in inorder)

#### Exercises with Processing Sequences

With your partner, determine the preorder, inorder, and postorder processing sequence for the tree below. Then, verify your answers below.

preorder:

A B C D E

inorder:

B A D C E

postorder:

B D E C A

#### A `BinaryTree` Class

The file `lab14/BinaryTree.java` defines a `BinaryTree` class and a `TreeNode` class. First, read the code, and predict what output will be produced by the statement

``print(t, "sample tree 2"); ``

Then provide a `fillSampleTree3` method that initializes the `BinaryTree` version of the tree pictured below.

#### Height Method

First, switch which partner is coding if you haven't recently.

Add a `height` method to the `BinaryTree` class, similar to the `AmoebaFamily` height method you worked with earlier. The height of an empty tree is 0; the height of a one-node tree is 1; the height of any other tree is 1 + the greater of the heights of the two children. You can use the buggy version as a starting point. Test your method on the various sample trees.

#### Is Completely Balanced

Then provide an `isCompletelyBalanced` method for the `BinaryTree` class. An empty tree and a tree containing just one node are both completely balanced; any other tree is completely balanced if and only if the height of its left child is equal to the height of its right child, and its left and right children are also completely balanced. Test your method on the various sample trees, as well as a completely balanced tree of height 3.

## D. Conclusion

#### Submission

You will submit your JUnit test, `AmoebaFamily.java` and `BinaryTree.java`.

Make sure you have completed the following methods in 'AmoebaFamily.java':

``````public void makeNamesLowercase();
public void replaceName(String currentName, String newName);
public void printFlat();
public void print();
public String longestName();
public int size();
public int height();``````

and in 'BinaryTree.java':

``````public void fillSampleTree3();
public int height();
public boolean isCompletelyBalanced();``````

In addition, please fill out this self-reflection form before this lab is due, as a part of your homework assignment. Self-reflection forms are to be completed individually, not in partnership.