Problem Set 8 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 5

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 inorder iterator. Can you give us any hints?

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

   We reviewed this class in Lab 12. In addition, 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 inorder iterator class.

   The constructor for your inorder iterator will be more complicated than the constructor for the preorder iterator, since an inorder traversal doesn’t necessarily begin with the root of the tree. You’ll need to iteratively navigate to the appropriate first node for a inorder 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 inorder 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.