Problem Set 9

part I due by 10 p.m. on Friday, July 31, 2026
part II due by 10 p.m. on Monday, August 3, 2026

Preliminaries

In your work on this assignment, make sure to abide by the policies on academic conduct for this course.

If you have questions while working on this assignment, please come to office hours, post them on Ed Discussion, or email cscis111-staff@lists.fas.harvard.edu

Part I

50 points total

Creating the necessary folder

Create a subfolder called ps9 within your s111 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

The problems from Part I will all be completed in a single PDF file. To create it, you should do the following:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps9_partI.

4. Add your work for the problems from Part I to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file on your machine. The resulting PDF file (ps9_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Tree traversal puzzles

10 points total; 5 points each part; individual-only

1. When a binary tree of characters (which is not a binary search tree) is listed in postorder, the result is GEIADJCBHF. Inorder traversal gives GIEDAFCJBH. Construct the tree by editing the diagram that we have provided in section 1-1 of ps9_partI:

   • Click on the diagram and then click the Edit link that appears below the diagram.

   • We have provided the necessary nodes and edges, but you will need to move them into the appropriate positions and connect them.

   • When you have completed your edits, click the Save & Close button.

2. When a binary tree of characters (which is not a binary search tree) is listed in preorder, the result is KEVBWLDGCJ. Inorder traversal gives VWBELKGCJD. Construct the tree by editing the diagram that we have provided in section 1-2 of ps9_partI.

Problem 2: Huffman encoding

8 points total; individual-only

Consider the following table of character frequencies:

1. (6 points) Show the Huffman tree that would be constructed from these character frequencies by editing the diagram that we have provided in section 2-1 of ps9_partI. It includes some of the necessary nodes and edges, but you should create more of them as needed, move them into the appropriate positions, and connect them.

2. (2 points) Using the Huffman tree from part 1, what will be the encoding of the string affect?

Problem 3: Binary search trees

10 points; 2 points each part; individual-only

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

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

2. What would be the output of a preorder traversal?

3. Show the tree as it will appear if 21 is inserted, followed by 60 by editing the diagram that we have provided in section 3-3 of ps9_partI.

We will cover the material needed for the remaining parts of this problem Thursday’s lecture.

4. Suppose we have the original tree and that 23 is deleted and then 44 is deleted, using the algorithm from the lecture notes. Show the final tree by editing the diagram that we have provided in section 3-4 of ps9_partI.

5. Is the original tree balanced? Explain briefly why or why not.

Problem 4: Finding the largest key less than a threshold

15 points total; 5 points each part; individual-only

We will cover material needed for parts of this problem in Thursday’s lecture.

The code below represents one algorithm for finding the largest key less than some threshold value t in an instance of our LinkedTree class. The maxLessThanInTree() method returns the largest key less than the specified threshold t in the tree/subtree whose root node is specified by the parameter root. The maxLessThan() method returns the largest key less than t in the entire tree represented by the LinkedTree object on which the method is invoked. For the purposes of this problem, we assume that all key values are positive. If there are no keys less than the specified threshold, both methods return -1.

private static int maxLessThanInTree(Node root, int t) {
    if (root == null) {
        return -1;
    } else {
        int maxInLeft = maxLessThanInTree(root.left, t);
        int maxInRight = maxLessThanInTree(root.right, t);
        int maxInSubtrees = Math.max(maxInLeft, maxInRight);
        if (root.key < t) {
            return Math.max(root.key, maxInSubtrees);
        } else {
            return maxInSubtrees;
        }
    }
}

public int maxLessThan(int t) {
    // make the first call to the recursive method,
    // passing in the root of the tree as a whole
    return maxLessThanInTree(root, t);
}

Note: The Math.max() method is a built-in static method that returns the larger of its two inputs.

Examples: Imagine that the variable tree referred to a LinkedTree object for the binary tree shown below:

Given this tree:

• tree.maxLessThan(80) would return 70
• tree.maxLessThan(37) would return 35
• tree.maxLessThan(60) would return 56
• tree.maxLessThan(10) would return -1

Your tasks

1. For a binary tree with n nodes, what is the time efficiency of the algorithm implemented above as a function of n? Use big-O notation, and explain your answer briefly.

   If the time efficiency depends on the keys in the tree or on the tree’s shape, you should explain why and give three big-O expressions: one for the best case, one for the worst case if the tree is balanced, and one for the worst case if the tree is not balanced. If the time efficiency does not depend on the keys or the shape of the tree, you should explain why and give one big-O expression.

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 maxLessThanInTree that does so. Your new method should avoid visiting nodes unnecessarily. In the same way that the search for a key doesn’t consider every node in the tree, your method should avoid considering subtrees that aren’t needed to determine the correct return value. Like the original version of the method above, your revised method should also 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 maxLessThanInTree() 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 copy of ps9_partI.

3. For a binary search tree with n nodes, what is the time efficiency of your revised algorithm as a function of n?

   Here again, if the time efficiency depends on the keys in the tree or on the tree’s shape, you should explain why and give three big-O expressions: one for the best case, one for the worst case if the tree is balanced, and one for the worst case if the tree is not balanced. If the time efficiency does not depend on the keys or the shape of the tree, you should explain why and give one big-O expression.

   Note: You are allowed to use the Math.max() method as the original version does.

Problem 5: 2-3 Trees

7 points; individual-only

Let’s say that you want to insert items with the following sequence of keys:

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

Insert this sequence into an initially empty 2-3 tree by editing the diagram that we have provided for Problem 5 of ps9_partI. Show the tree after each insertion that causes a split of one or more nodes, and the final tree.

We have given you a sample diagram that includes nodes of different sizes. Make copies of the diagram so that you can use separate diagrams for the results of each insertion that causes a split, and for the final tree. Note that you do not need to keep the shape of the tree that we have given you. Rather, you should edit it as needed: deleting or adding nodes and edges, replacing the Xs with keys, adding or removing keys, and making whatever other changes are needed.

Note: Problems on heaps and hash tables will be included in Problem Set 10.

Submitting your work for Part I

Submit your ps9_partI.pdf file by taking the following steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file on your machine.

2. Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Part II

50-60 points total

Preparing for Part II

1. You should begin by downloading the following zip file:
   ps9_partII.zip

2. Unzip/extract the contents of the file.

3. Depending on your system, after extracting the contents you will either have:

   • a folder named ps9_partII that contains all of the files that you need for the problems in Part II

   • an outer folder called ps9_partII that contains an inner folder named ps9_partII that contains all of the Java files that you need.

   Take the ps9_partII folder that actually contains the necessary files and drag it into your ps9 folder so that you can easily find and open it from within VSCodium.

4. In VSCodium, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open the ps9_partII folder that you created above – the one that contains the provided files. (Note: You must open the folder; it is not sufficient to simply open one of the Java files in the folder.)

   The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with a list of all of its contents.

Problem 6: Adding methods to the LinkedTree class

25 points

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

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

1. Write a non-static minOnPathTo(int key) method that takes takes an integer key as its only parameter and that uses uses iteration to determine and return the smallest key on the path from the root node to the node with the specified key. Your method should take advantage of the fact that the tree is a binary search tree when determining which path to follow. 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 examples of minOnPathTo(). To help you visualize the tree, it’s worth noting that we’re using an array of keys that produces the following binary tree:

   

   If we run the following test code:

   LinkedTree tree = new LinkedTree();
   System.out.println("result 1 = " + tree.minOnPathTo(13));
   int[] keys = {37, 26, 42, 13, 35, 56, 30, 47, 70};
   tree.insertKeys(keys);
   System.out.println("result 2 = " + tree.minOnPathTo(13));
   System.out.println("result 3 = " + tree.minOnPathTo(35));
   System.out.println("result 4 = " + tree.minOnPathTo(37));
   System.out.println("result 5 = " + tree.minOnPathTo(50));
   

   we should see the following results:

   result 1 = -1
   result 2 = 13
   result 3 = 26
   result 4 = 37
   result 5 = -1
   

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

   • a private static method called numOddInTree() that takes a reference to a Node object as its only parameter; it should use recursion to find and return the number of odd keys in the binary search tree or subtree whose root node is specified by the parameter. Make sure that your method correctly handles empty trees/subtrees – i.e., cases in which the value of the parameter root is null.

   • a public non-static method called numOdd() that takes no parameters and that returns the number of odd keys in the entire tree. This method should serve as a “wrapper” method for numOddInTree(). 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, if we run the following tests, which use the same keys array as the one given above:

   LinkedTree tree2 = new LinkedTree();
   System.out.println("count 1 = " + tree2.numOdd());
   int[] keys = {37, 26, 42, 13, 35, 56, 30, 47, 70};
   tree2.insertKeys(keys);
   System.out.println("count 2 = " + tree2.numOdd());
   

   we should see:

   count 1 = 0
   count 2 = 4
   

3. Write a non-static method deleteMin() that takes no parameters and that uses iteration to find and delete the node containing the smallest 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. Your method should take advantage of the fact that the tree is a binary search tree.

   Important: Your deleteMin() 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 smallest node may have.

   For example, if we run the following tests using the same keys array as above:

   LinkedTree tree3 = new LinkedTree();
   System.out.println("empty tree: " + tree3.deleteMin());
   
   int[] keys = {37, 26, 42, 13, 35, 56, 30, 47, 70};
   tree3.insertKeys(keys);
   System.out.println("levels of original tree:");
   tree3.levelOrderPrint();
   
   System.out.println("\ndeleteMin: " + tree3.deleteMin());
   tree3.levelOrderPrint();
   System.out.println("\ndeleteMin: " + tree3.deleteMin());
   tree3.levelOrderPrint();
   

   we should see:

   empty tree: -1
   levels of original tree:
   37
   26 42
   13 35 56
   30 47 70
   
   deleteMin: 13
   37
   26 42
   35 56
   30 47 70
   
   deleteMin: 26
   37
   35 42
   30 56
   47 70
   

   Note that first we delete 13, because it is the smallest key in the original tree. Next we delete 26, because it is the smallest remaining key. As a result of these deletions, 35 and 30 move up a level in the tree.

4. Writing well-formatted units tests is an extremely important part of a programmer’s work. In the main() method of LinkedTree.java, we’ve given you an example of what such a unit test should look like.

   Update the main() method to include at least two unit tests for each of your new methods. Your unit tests must follow the same format as our example test. In particular, the output of each of your unit tests should include:

   • a header that specifies the test number and a description of what is being tested
   • the actual return value that you get from that test
   • the expected return value
   • whether the actual return value matches the expected return value.

   Put each test in the context of a try-catch block so that you can handle any exceptions that are thrown. Leave a blank line between tests.

   Additional notes:

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

   • Our model unit test can be used to test the maxLessThanInTree()/maxLessThan() methods from Problem 4.

Problem 7: Binary tree iterator

25 points; pair-optional

We will cover material that will be helpful for this problem in section.

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. 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.

   The version of LinkedTree that we discussed in lecture did not include parent references, but we’ve included them in the copy of LinkedTree.java that we’ve given you for this assignment, and it is important that you start by reviewing the code that we’ve added for this purpose:

   1. First, note that we have added a field called parent to the inner Node class:

      private class Node {
          private int key;    
          private LLList data;
          private Node left;
          private Node right;
          private Node parent;     // added for Problem 7
          ...
      

      This new parent field is assigned a value of null by the Node constructor. It doesn’t actually point to the node’s parent until the Node object is added to the tree by the insert method.

   2. As discussed in lecture, the insert method makes use of a local variable named parent that serves as a trailing reference during the search for the key that is being inserted. At the end of that search, the local variable parent holds a reference to the Node object that is about to become the parent of the new node. As a result, we are able to set the value of the new node’s parent field by using the following line of code at the very end of the insert method:

      newNode.parent = parent;
      

      Note: When we insert an item into an empty tree, the local variable parent will be null at the end of the insert method, and thus we will end up assigning null to newNode.parent. This makes sense, because when we add a node to an empty tree, it becomes the root of the entire tree, and thus its parent field should have a value of null!

   3. When a node that has one child is deleted, that child’s parent changes. This change is handled by the following lines, which have been added to the middle of the deleteNode method:

      if (toDeleteChild != null) {
          toDeleteChild.parent = parent;
      }
      

1. The deleteMin method that you implemented for Problem 6 can also change the parent of a node in some cases. Update your deleteMin method so that it correctly updates the parent field of the affected Node object in such cases.

2. Review the code that we’ve given you in the PreorderIterator class and the preorderIterator() method, and understand how that iterator works. We will review this iterator in section, and we have also provided an overview of it here.

3. 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.

4. 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 an 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.

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

6. 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.

7. Add an 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.

8. 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.

There are no grad-credit problems for this assignment.

Submitting your work for Part II

Coming soon!

Last updated on July 30, 2026.