Problem Set 7

due by 11:59 p.m. on Tuesday, April 16, 2019

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email instructor.

Make sure to submit your work following the procedures found at the end of the assignment.

Important: Begin this problem set by first doing a thorough review of the lecture material on trees, binary search trees and balanced trees (to be covered week of 4/9). Additionally, it will be very beneficial to review Java iterators for a thorough understanding of how we used an iterator in the LLList class. You will need to implement an iterator on a search tree in Part II.

As this problem set is very extensive, we have provided an FAQ which may assist and clarify any immediate questions you may have.

Part I

50 points total

Problem 1: Binary tree basics

14 pts. total; individual-only

Put all of your work for this problem in a plain-text file named ps7pr1.txt.

Consider the following binary tree, in which the nodes have the specified integers as keys:

1. What is the height of this tree?

2. How many leaf nodes does it have? How many interior nodes?

3. If a preorder traversal were used to print the keys, what would the output be?

4. What would be the output of a postorder traversal?

5. What would be the output of a level-order traversal?

6. Is this tree a search tree? Explain briefly why or why not.

7. Is this tree balanced? Explain briefly why or why not.

Problem 2: Binary search trees

8 pts. total; 4 pts. each part; individual-only

Put all of your work for this problem in a PDF file named ps7pr2.pdf. See below for details on how to create the PDF file.

Consider the following tree, which is a binary search tree.

1. Show the tree as it will appear if 25 is inserted, followed by 51.

   To do so, you should:

   • Open the template that we have created
     for this problem in Google Docs.

   • Select File->Make a copy..., and save the copy to your Google Drive using the name ps7pr2.

   • Edit the first diagram by clicking on it and then clicking the Edit link that appears below the diagram.

   • Add the necessary nodes and edges to the tree. One way to do so is to copy and paste existing nodes and edges, and to change the key values inside the copies of the nodes. Feel free to move existing nodes as needed to make room.

   • Click the Save & Close button.

2. Suppose we have the original tree and that 53 is deleted and then 35 is deleted, using the algorithm from the lecture notes. Show the final tree by editing the second diagram in your copy of the Google Doc.

Once you have made all of the necessary edits to your copy of the Google Doc, choose File->Download as->PDF Document, and save the PDF file on your machine.

Problem 3: Tree traversal puzzles

8 points total; 4 points each part

Put all of your work for this problem in a PDF file named ps7pr3.pdf. See below for details on how to create the PDF file.

1. When a binary tree of characters (which is not a binary search tree) is listed in postorder, the result is ENIMOPTFRW. Inorder traversal gives IENWOMRPFT. Construct the tree.

   • Open our template for this problem, make a copy of it, and save it to your Google Drive using the name ps7pr3.

   • Edit the first diagram. It includes the necessary nodes and edges, but you will need to move them into the appropriate positions and connect them.

2. When a binary tree of characters (which is not a binary search tree) is listed in preorder, the result is TRMESBONVY. Postorder gives ESMRVYNOBT. Construct the tree by editing the second diagram in the Google Doc. (There is more than one possible answer in this case.)

Once you have made all of the necessary edits to your copy of the Google Doc, choose File->Download as->PDF Document, and save the PDF file on your machine.

Problem 4: Determining the depth of a node

12 points total; 4 points each part; individual-only

Put all of your work for this problem in a plain-text file named ps7pr4.txt.

The code below represents one algorithm for finding the depth of a node in an instance of our LinkedTree class from lecture.

The recursive depthInTree() method takes two parameters – an integer key and the root of a tree/subtree – and it returns the depth in that tree/subtree of the node with the specified key. It is a private static method that can only be called from within the class.

The separate depth() method is a “wrapper” method that makes the initial call to depthInTree(), passing in the root of the tree as a whole and returning whatever value depthInTree() returns – which will be the depth in the entire tree of the node with the specified key.

If the key is not found, the methods return -1.

public int depth(int key) {
    if (root == null) {    // root is the root of the entire tree
        return -1;
    }

    return depthInTree(key, root);
}

private static int depthInTree(int key, Node root) {
    if (key == root.key) {
        return 0;
    }

    if (root.left != null) {
        int depthInLeft = depthInTree(key, root.left);
        if (depthInLeft != -1) {
            return depthInLeft + 1;
        }
    }

    if (root.right != null) {
        int depthInRight = depthInTree(key, root.right);
        if (depthInRight != -1) {
            return depthInRight + 1;
        }
    }

    return -1;
}

1. For a binary tree with n nodes, what is the time complexity of this algorithm as a function of n in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.

2. If the tree is a binary search tree, we can revise the algorithm to take advantage of the ways in which the keys are arranged in the tree. Write a revised version of depthInTree that does so. Your new method should avoid considering subtrees that couldn’t contain the specified key. Like the original version of the method above, your revised method should be recursive.

   Note: In the files that we’ve given you for Part II, the LinkedTree class includes the methods shown above. Feel free to replace the original depthInTree() method with your new version so that you can test its correctness. However, your new version of the method should ultimately be included in your ps7pr4.txt file.

3. For a binary search tree with n nodes, what is the time complexity of your revised algorithm in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.

Problem 5: 2-3 trees and B-trees

8 points; 4 points each part

We will cover material needed for this problem during during the week of April 7th.

Put all of your work for this problem in a PDF file named ps7pr5.pdf. See below for details on how to create the PDF file.

Illustrate the process of inserting the key sequence

J, E, I, H, C, F, B, G, D, A

into:

1. an initially empty 2-3 tree

2. an initially empty B-tree of order 2

In both cases, show the tree after each insertion that causes a split of one or more nodes, and the final tree.

• Open our template for this problem, make a copy of it, and save it to your Google Drive using the name ps7pr5.

• We have given you sample diagrams that include nodes with more than one key. For each part of the problem, make copies of the diagram for that part within the Google Doc so that you can use separate diagrams for the results of each split, and for the final tree.

• Edit the copies of the diagrams: deleting or adding nodes and edges, changing the key(s) within a given node, and changing the size of a node as needed.

Once you have made all of the necessary edits to your copy of the Google Doc, choose File->Download as->PDF Document, and save the PDF file on your machine.

Part II

50 points total

Preparing for Part II

Begin by downloading the following zip file: ps7.zip

Unzip this archive, and you should find a folder named ps7, and within it the files you will need for Part II. Make sure that you keep all of the files in the same folder.

Problem 6: Adding methods to the LinkedTree class

25 points; individual-only

Make sure to begin by following the instructions given above under Preparing for Part II.

In the file LinkedTree.java, add code that completes the following tasks:

1. Write a non-static depthIter() method that takes takes an integer key as its only parameter and that uses uses iteration to determine and return the depth of the node with that key. Like the recursive method that you wrote for Problem 4, your iterative method should take advantage of the fact that the tree is a binary search tree, and it should avoid considering subtrees that couldn’t contain the specified key. It should return -1 if the specified key is not found in the tree.

   Note: There are two methods in the LinkedTree class that can facilitate your testing of this method and the other methods that you’ll write:

   • The insertKeys() method takes an array of integer keys, and it processes the array from left to right, adding a node for each key to the tree using the insert() method. (The data associated with each key is a string based on the key, although our tests will focus on just the keys.)

   • The levelOrderPrint() method performs a level-order traversal of the tree and prints the nodes as they are visited; each level is printed on a separate line. This method doesn’t show you the precise shape of the tree or the edges between nodes, but it gives you some sense of where the nodes are found.

   For example, below are some tests of depthIter(). To help you visualize the tree, it’s worth noting that we’re using an array of keys that produces the binary search tree shown in Problem 2.

   > LinkedTree tree = new LinkedTree();
   > System.out.println( tree.depthIter(48) );
   -1
   > int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   > tree.insertKeys(keys);
   > tree.levelOrderPrint();
   44 
   35 53 
   23 48 62 
   28 57 80 
   > System.out.println( tree.depthIter(48) );
   2
   > System.out.println( tree.depthIter(28) );
   3
   > System.out.println( tree.depthIter(44) );
   0
   > System.out.println( tree.depthIter(30) );
   -1
   

2. Write two methods that together allow a client to determine the number of even keys in the tree:

   • a private static method called numEvenKeysRec() that takes a reference to a Node object as its only parameter; it should use recursion to find and return the number of even keys in the binary search tree or subtree whose root node is specified by the parameter.

   • a public non-static method called numEvenKeys() that takes no parameters and that returns the number of even keys in the entire tree. This method should serve as a “wrapper” method for numEvenKeysRec(). It should make the initial call to that method – passing in the root of the tree as a whole – and it should return whatever value that method returns.

   For example:

   > LinkedTree tree = new LinkedTree();
   > System.out.println( tree.numEvenKeys() );
   0
   > int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   > tree.insertKeys(keys);
   > System.out.println( tree.numEvenKeys() );
   5
   

3. Write a non-static method deleteMax() that takes no parameters and that uses iteration to find and delete the node containing the largest key in the tree; it should also return the value of the key whose node was deleted. If the tree is empty when the method is called, the method should return -1.

   Important: Your deleteMax() method may not call any of the other LinkedTree methods (including the delete() method), and it may not use any helper methods. Rather, this method must take all of the necessary steps on its own – including correctly handling any child that the largest node may have.

   For example:

   > LinkedTree tree = new LinkedTree();
   > tree.deleteMax()
   -1
   > int[] keys = {44, 35, 53, 23, 48, 62, 28, 57, 80};
   > tree.insertKeys(keys);
   > tree.levelOrderPrint();
   44 
   35 53 
   23 48 62 
   28 57 80 
   > System.out.println( tree.deleteMax() );
   80
   > tree.levelOrderPrint();
   44 
   35 53 
   23 48 62 
   28 57 
   > System.out.println( tree.deleteMax() );
   62
   > tree.levelOrderPrint();
   44 
   35 53 
   23 48 57
   28
   

   Note that first we delete 80, because it is the largest key in the original tree. Next we delete 62, because it is the largest remaining key. As a result of these deletions, 57 moves up a level in the tree, because it is now the child of 53.

4. In the main() method, add at least two unit tests for each of your new methods.

   • For part 2 (numEvenKeysRec()/numEvenKeys()), your unit tests only need to call numEvenKeys(), since doing so will also call numEvenKeysRec().

   • Use the same unit-test format that we specified in PS 6, Problem 6.

   • We have given you a model unit test in main() that tests the depth()/depthInTree() methods from Problem 4. Note that these methods are distinct from the depthIter() method that you are writing for this problem.

Problem 7: Binary tree iterator

25 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

The traversal methods that are part of the LinkedTree class are limited in two significant ways: (1) they always traverse the entire tree; and (2) the only functionality that they support is printing the keys in the nodes. Ideally, we would like to allow the users of the class to traverse only a portion of the tree, and to perform different types of functionality during the traversal. For example, users might want to compute the sum of all of the keys in the tree. In this problem, you will add support for more flexible tree traversals by implementing an iterator for our LinkedTree class.

You should use an inner class to implement the iterator, and it should implement the following interface:

public interface LinkedTreeIterator {
    // Are there other nodes to see in this traversal?
    boolean hasNext();

    // Return the value of the key in the next node in the
    // traversal, and advance the position of the iterator.
    int next();
}

There are a number of types of binary-tree iterators that we could implement. We have given you the implementation of a preorder iterator (the inner class PreorderIterator), and you will implement a postorder iterator for this problem.

Your postorder iterator class should implement the hasNext() and next() methods so that, given a reference named tree to an arbitrary LinkedTree object, the following code will perform a complete postorder traversal of the corresponding tree:

LinkedTreeIterator iter = tree.postorderIterator();
while (iter.hasNext()) {
    int key = iter.next();

    // do something with key
}

Here are the tasks that you should perform:

0. Review the code that we’ve given you in the PreorderIterator class and the preorderIterator() method, and understand how that iterator works. It’s worth noting that you can’t actually use a PreorderIterator object yet, because it will only work after you have completed the next task.

1. In order for an iterator to work, it’s necessary for each node to maintain a reference to its parent in the tree. These parent references will allow the iterator to work its way back up the tree.

   In the copy of LinkedTree.java that we’ve given you for this assignment, the inner Node class includes a field called parent, but the LinkedTree code does not actually maintain this field as the tree is updated over time. Rather, this parent field is assigned a value of null by the Node constructor, and its value remains null forever.

   Before implementing the iterator, you should make whatever changes are needed to the existing LinkedTree methods so that they correctly maintain the parent fields in the Node objects.

   • For example, when a Node object is first inserted in the tree, you should set its parent field to point to the appropriate parent node.

   • Think about when the parent of a node can change, and update the necessary method(s) to modify the parent field in a Node object whenever its parent changes.

   • The root of the entire tree should have a parent value of null.

2. Next, add a skeleton for your iterator class, which you should name PostorderIterator (note that only the P and I are capitalized). It should be a private inner class of the LinkedTree class, and it should implement the LinkedTreeIterator interface. Include whatever private fields will be needed to keep track of the location of the iterator. Use our PreorderIterator class as a model.

3. Implement the constructor for your iterator class. Make sure that it performs whatever initialization is necessary to prepare for the initial calls to hasNext() and next().

   In the PreorderIterator constructor that we’ve given you, this initialization is easy, because the first node that a preorder iterator visits is the root of the tree as a whole. For a postorder iterator, however, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the postorder iterator should visit, and initialize the iterator’s field(s) accordingly.

4. Implement the hasNext() method in your iterator class. Remember that it should execute in O(1) time.

5. Implement the next() method in your iterator class. Make sure that it includes support for situations in which it is necessary to follow one or more parent links back up the tree, as well as situations in which there are no additional nodes to visit. If the user calls the next() method when there are no remaining nodes to visit, the method should throw a NoSuchElementException.

6. Add a postorderIterator() method to the outer LinkedTree class. It should take no parameters, and it should have a return type of LinkedTreeIterator. It should create and return an instance of your new class.

7. Test everything! At a minimum, you must do the following: In the main() method, add a unit test that uses the while-loop template shown near the start of this problem to perform a full postorder traversal of a sample tree.

Submitting Your Work

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;

• You have removed or changed all comments inherited from my templates which do not relate to your solution;

• ensured that the signature of the methods specified in the assignment have not been changed.

• You have verified that your programs satisfy all the performance tests in the templates;

Follow the instructions and submit the following files:

• your ps7pr1.txt file for Problem 1
• your ps7pr2.pdf file for Problem 2
• your ps7pr3.pdf file for Problem 3
• your ps7pr4.txt file for Problem 4
• your ps7pr5.pdf file for Problem 5
• your modified LinkedTree.java file containing your work on Problems 6 and 7; if you worked with a partner on Problem 7, make sure that you each submit a copy of your joint work on that problem, and that you include comments at the top of each file specifying the name and email of your partner