Problem Set 7 FAQ

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

Problem 3

1. Can you recommend a systematic way of attacking these puzzles, or is trial-and-error the only viable approach?

   As mentioned in lecture, there is certain information about the tree that you can immediately glean by looking at the pairs of traversals we give you. For example, what must be true of the last node listed in a postorder traversal? The first node in a postorder traversal? What can you say about the node listed just before the root node in an inorder traversal? By asking such questions you should be able to get at least a rough idea of what the tree looks like, and you can then use trial-and-error to fill in the missing pieces.

   Also, don’t forget that whatever applies to the tree as a whole must also apply recursively to any subtree of the tree. See if you can use what you know about the traversals to determine the left and right subtrees of the root, and then apply the same reasoning to each subtree.

2. Problem 3, part 1 seems to be incorrect. Shouldn’t the inorder traversal have visited the keys in alphabetical order?

   No. The tree in this question isn’t a binary search tree, so an inorder traversal won’t necessarily visit the nodes according to the values of their keys.

Problem 5

1. Should we sort the keys before inserting them?

   No! They should be inserted in the order in which we listed them: first J, then E, etc.

2. How are letter keys compared in a search tree?

   They are compared based on where they fall in the alphabet. A key that comes earlier in the alphabet is smaller than a key that comes later in the alphabet. When in doubt, you can compare char values in the DrJava Interactions Pane. For example:

   > 'A' < 'J'
   true
   

3. Why are there numbers instead of letters in the template that you gave us?

   The template has numbers because we didn’t want you to think that we were giving you part of the answer. You should use the node shapes that we’ve given you to build your own trees and change the keys to the appropriate letters.

Problem 6

1. Can our methods for Problem 6 make use of the parent fields in the nodes (the ones that we are adding support for in Problem 7)?

   Yes, although doing so is not required.

   If you choose to use the parent fields in one or more of your Problem 6 methods, you will also need to ensure that your Problem 6 methods correctly maintain those parent fields. In other words, if one of your Problem 6 methods changes the parent of a node, you would need to update its parent field accordingly.

   If you choose to not use the parent fields in Problem 6, then you won’t need to worry about having your Problem 6 methods correctly maintain the parent fields.

   In either case, you will need to ensure that the methods in the original version of the LinkedTree correctly maintain the parent fields, as described in Task 1 of Problem 7.

Problem 7

1. I’m having difficulty with Task 1 – initializing and maintaining the new parent fields in the Node objects. Do you have any suggestions?

   We have already indicated that you should set this parent field when the Node object is first inserted in the tree. You will need to add the appropriate code to the method that inserts the node.

   In addition, you should ask yourself when (in what methods) does a Node‘s parent change? Add the appropriate code to update the parent field in those methods.

   One caution: some of the existing LinkedTree methods actually use a variable called parent. This variable is a local variable, and it is not the same thing as the parent field in the Node object.

2. I’m having difficulty implementing the class for the postorder iterator. Can you give us any hints?

   You should start by studying the code for the PreorderIterator inner class that we’ve given you.

   To assist you in this process, we have created an overview of that class that we encourage you to read.

   You should use the PreorderIterator class as a template for the overall structure of your postorder iterator class.

   The constructor for your postorder iterator will be more complicated than the constructor for the preorder iterator, since an postorder traversal doesn’t necessarily begin with the root of the tree. You’ll need to iteratively navigate to the appropriate first node for a postorder traversal, and initialize your instance variable(s) so that that node’s key will be returned by the first call to next().

   Your next() method itself should have the same basic structure as the next() method in the PreorderIterator class. However, at least some of the cases that you’ll need to handle will be different. different.

   To determine what the relevant cases are, we encourage you to trace through a postorder traversal of some example binary trees on paper. At each node in the traversal, ask yourself what operations need to be performed to get to the next node in the traversal. You should soon find that these operations fall into a relatively small number of categories. These will become the branches of the if-else-if-else statement that you write for the next() method.

   If you find that you have a large number of cases, or your class is substantially longer than the PreorderIterator class, you’re probably on the wrong track.

3. Does our next() method need to have a time complexity of O(1)?

   No. It will sometimes be necessary to follow a path up or down the tree. This can’t be done in O(1) time since it depends on the height of the tree. However, your next() method should be as time-efficient as you can make it, and your iterator class as a whole should have a space complexity of O(1). And as the problem states, your hasNext() method does need to run in O(1) time.

4. **What name is the method for creating the iterator supposed to have? In the while-loop template that you gave us near the beginning of Problem 7, the method is called postIterator(), but in Task 6 of Problem 7, it is called postorderIterator().

   It should be called postorderIterator() as instructed in Task 6, and we have updated the while-loop template accordingly. Sorry for the confusion.