CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 5

To Be Turned In

Except where noted, these are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

  1. (5 points) Consider a PostOrder iterator (see Weiss §18.4) for the binary tree shown on page 657 (Figure 19.34). Using the notation of Figure 18.25, show the contents of the stack at the time when 55 is the node whose value is about to be output.

  2. (10 points) If tree is a BinaryTree with N nodes, and itr is a PostOrder iterator for that tree, suppose that we run the following code: 

    for (itr.first(); itr.isValid(); itr.advance()) {
	System.out.println(itr.retrieve());
}

    Is the running time for this code Θ(log N), Θ(N), Θ(N log N) or Θ(N2)?

    Explain your answer.

    Be sure that your explanation accounts for how the postorder iterator’s stack is used during the execution of the code. The code for the PostOrder class can be found in Section 18.4 (spanning three different pages).

  3. (40 points) This problem, though part of the written assignment, involves actually getting your code working on your computer. But, since it requires you to write a very small amount of code, and the thought process involved is more along the lines of written problems in this course, I am including it in a written assignment.

    When it comes to implementing ordered sets, Binary Search Trees are generally better than array lists or linked lists, because many O(n) operations on lists or vectors become (on average) O(log n) on BSTs. But there is at least one operation that is less efficient in most cases on a BST than on a list: given an element of the structure, find the next or previous in-order element of the structure. This is especially true for nodes in the BST that have no children. Weiss’s InOrder iterator class (page 594) has to maintain an auxiliary stack in order to be able to do the next advance(). It would also be nice to be able to have a retreat() method in the InOrder class as well. A call to advance() moves the current position to the in-order successor of the current node, while a call to retreat() would move to the in-order predecessor of the current node. The obvious approaches to efficiently supporting both advance() and retreat() require a lot of extra space and time. So let’s try an un-obvious approach.

    There is a well-known way to make these operations more efficient. We can take advantage of the fact (we will prove it later) that more than half of the references in a binary tree are null. We replace each null left reference in the tree by a reference to that node’s in-order predecessor, and replace each null right reference by a reference to the node’s in-order successor. Traditionally, these in-order references have been called threads (same word but no relation to “threads of execution”). If we use threads, we need to be able to distinguish a thread from a regular left or right pointer. Doing so only requires two additional bits in each node , although it’s easier to write the code (and thus we do it here) with two boolean instance variables, isLeftThread and isRightThread. When one of these fields contains true, it indicates that the corresponding reference in the node is a thread, rather than a “normal” tree pointer.

    You can do the problem without reading this note; it is here for your edification. Generally there would be some field of the node that does not really use all of the bits allotted to it, and some masking would allow us to grab two of the bits of that field to use for the “is it a thread” information without taking up any extra space. In a language (like C or C++) that allows typecasting between integers and pointers, we can always do this: The value of a pointer will probably always end in two 0 bits (because things “pointed to” will be aligned on longword boundaries); we could use those bits “for free.” That is, the extra space would come at no cost. But this approach obviously requires more time.

    In the diagram below, normal pointers are shown as solid lines, while threads are dotted lines. The threads from the left- and right-most nodes represent null references. These two null references could be treated either as threads or regular pointers, but since the former makes the code that you will write easier, the diagram shows them as threads.

    I am providing a complete ThreadedBinaryNode class and JUnit tests in ThreadedBinarySearchTreeTest. To help you with debugging, I’m also providing a TestThreadedTree class that prints results rather than doing unit tests. The file expected_output_of_TestThreadedTree.txt gives the results of a correct run of TestThreadedTree. While these printed results should be useful for debugging, the JUnit tests are what we will use to judge the correctness of your code.

    Your job is to complete the ThreadedBinarySearchTree class. I provided part of the class to help you get oriented, so you only have to write three methods (insert, toStringInOrder, and toStringInReverseOrder). In fact, we have provided the driver for insert; you only need to write the recursive helper method that does the real work.

    In order to get full credit, you must meet the following constraints:

    1. insert must have running time that is O(height of the tree).
    2. toStringInOrder and toStringInReverseOrder must not use a stack (nor any other collection, including an array) or recursion.
    3. The code that you write for toStringInOrder and toStringInReverseOrder may not reference root at all. (That is, you can leave in the two given references to root but must not add any others).

    Ideally, ThreadedBinarySearchTree would implement the entire SortedSet interface. But that would have made this problem too long and complicated for a small exercise. So I am only having you implement two methods that are similar to methods from that interface.

    Also, it would be desirable to implement ThreadedInOrder, an in-order iterator class for ThreadedBinarySearchTree. But I did not want to add the complication of having you write yet another class, so I chose to settle for the toStringInOrder and toStringInReverseOrder methods, which bring out the same threading issues.

    Getting the code: The starting code is available in your SVN repository in the Threaded project. Treat the comments in that code as part of the requirements for this problem.

    I suggest that you begin by studying the ThreadedBinaryNode class. Notice that this class and its fields are package protected. In order to facilitate debugging, I have written an unusual toString() method for the ThreadedBinaryNode class. It shows the node’s contents, the contents of its left and right “children”, and the value of its boolean isLeftThread and isRightThread fields. This toString() method should be called whenever you need to a text representation of a node’s contents.

    You should also study the ThreadedBinarySearchTree class. It has a single instance variable, root of type ThreadedBinaryNode. No explicit constructor is needed; the default constructor does what we need. Study the provided find() method and its recursive helper method as an example of how to work with the threads.

    Testing: TestThreadedTree is just provided for your convenience. The JUnit tests in ThreadedBinarySearchTreeTest are how we will evaluate the correctness of your program.

    Turnin: Commit to your repository.

    When we run your program for grading purposes, we may alter TestThreadedTree to use some different input strings, but we will not change it in any other way (unless someone points out an error and I notify you in advance of the due date).