In problem 1 (tree traversal puzzles), can you recommend a systematic way of attacking the problem, 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.
Problem 1, part 1 seems to be incorrect. Shouldn’t the inorder traversal have visited the keys in alphabetical order?
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.
In problem 7, 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 we’ve given you. We’ve provided you with an
overview of that class, and we also discussed
it during section. 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 preorder iterator class. However, the
cases you’ll need to consider in your if statement may be
different. For a preorder traversal, we determined that there were 3
cases to consider:
When trying to determine what cases need to be dealt with in the
inorder version of next(), it might help 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 statement 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.
For problem 7, does our next() method need to have a
time complexity of O(1)?
No. It will sometimes be necessary to follow one or more parent
links back up the tree in your next() method, something that 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. Efficiency will be a
non-trivial part of your grade for this problem.
Last updated on October 28, 2025.