Trees

Today, we will explore how to implement hierarchical structures, trees, in Java.

Setup

Create a new lab repository for this week using our template for Maven-based Java projects. You should use this template repository to create a new repository on your account, giving the repo an appropriate name for this week’s work, e.g., trees.

https://github.com/Tools-for-Thinking-About-Programs/java-maven-template

Once you have created and locally cloned your repository, add the following files, taking care to ensure that you add them to folders consistent with their declared packages, edu.ttap.trees. (Recall that regular source files go under the src/main/java path and test files go under the src/test/java path.)

Part 1: Contains

First, let’s implement a basic recursive operation over a tree from scratch. Tree.contains(T v) returns true if and only if (iff) v is contained within the given tree.

Give an algorithmic description of contains based on the recursive definition of a binary tree.
Translate that description into an implementation for the contains method and verify that your implementation works for the tests found in TreeTests.java.

Part 2: Traversals

In the reading, we discussed three different kinds of traversals: preorder, in-order, and post-order traversals. The reading describes them as follows:

A preorder traversal “visits” the value at the node, the left subtree, and then the right subtree.
An in-order traversal “visits” the left subtree, the value at the node, and then the right subtree.
A post-order traversal “visits” the left subtree, the right subtree, and then the value at the node.

First, start with in-order traversals:

Write down a description of the preorder traversal algorithm using the recursive definition of a binary tree, i.e., in terms of leaf and node cases.
Implement Tree.toListInorder() based on this description. (Hint: your recursive helper function will take an additional argument, a list that you will add the elements into. This list should initially be empty.)
Verify that your implementation passes the tests.

After you do this:

Adapt your algorithmic description of in-order traversal to preorder and post-order traversal. Specifically, how does the description change based on which traversal you are specifying?
With this insight, implement Tree.toListPreorder() and Tree.toListPostorder(). You should find that implementing these methods are trivial provided you have implemented toListInorder() correctly! Make sure that your code passes all tests!

Part 3: Stringifying Trees

Now, let’s implement a recursive operation that requires some additional case work. Recall that when we wrote a pretty printing function for an array, we (essentially) needed a special case for the first element of the list. This is because a comma-separated list of $n$ elements only has $n - 1$ commas.

import java.util.StringBuffer;

public static void arrayToString(int[] arr) {
    StringBuffer buf = new StringBuffer("[");
    if (arr.length > 0) {
        buf.append(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            buf.append(", ");
            buf.append(arr[i]);
        }
    }
    buf.append("]");
    return buf.toString();
}

Observe how in arrayToString we treat the first element of the array specially (i.e., add it to the string without a comma). Every other element v in the array can then be appended as ", v". Also note how we use a StringBuffer rather than naive string concatenation to avoid the classic $O (n^{2})$ time complexity problem associated with incrementally building an immutable string.

Adapt this approach to implement Tree.toString() which returns a String representation of the elements of tree in a linearized form: [v1, ..., vk]. To do so, you should treat the “first” element of the tree, i.e., the root, specially, similar to the first element of the array in arrayToString.

Give an algorithmic description of toString based on the recursive definition of a binary tree.
Modify the test for calling toString on the example tree based on how you predict your toString method will behave.
Translate that description into an implementation for toString method and verify it passes the tests.

For Additional Practice: Pretty Printing

Observe that our toString method linearized the tree, losing its hierarchical structure. This is convenient for a quick implementation, but we might want to visualize the hierarchical structure within a tree. We can use a bulleted-list style representation where we use indentation and sub-bullets to capture parent-children relationships. For example, we might visualize our example tree in this style as follows:

Write a method toPrettyString() that returns a string representation of a tree in this format.

(Hint: you will need to keep track of the indentation level in your recursion. This amounts to including an extra parameter in your recursive helper function!)