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 seems to be incorrect. Shouldn’t the inorder traversal have visited the keys in alphabetical order?
The trees in this question are not binary search trees, 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 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 iterator class.
The constructor for your iterator will be more complicated
than the constructor for the preorder iterator, since its
traversal won’t necessarily begin with the root of the
tree. You’ll need to iteratively navigate to the appropriate
first node for this type of iterator, and initialize your
field(s) so that the first 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:
the current node has a left child (in which case the next node to visit is the left child)
the current node has no left child, but has a right child (in which case the next node to visit is the right child)
the current node is a leaf node (in which case we need to back up the tree and find a node with a right child not on the path to the current node)
When trying to determine what cases need to be dealt with in
your iterator’s version of next(), it might help to trace
through traversals of some example binary trees on
paper. At each node in a 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 July 29, 2026.