Answers to Self-Check Problems - Building Java Programs: A Back to Basics Approach - page 1102

20. Here is the resulting tree:

Lisa

Bart Marge

Homer Maggie Smithers

Flanders Milhouse

Preorder: Lisa, Bart, Homer, Flanders, Marge, Maggie, Smithers, Milhouse

Inorder: Bart, Flanders, Homer, Lisa, Maggie, Marge, Milhouse, Smithers

Postorder: Flanders, Homer, Bart, Maggie, Milhouse, Smithers, Marge, Lisa

21. The add method needs to return the newly added node to enable the x =
change(x) pattern. If no reference to the new node is returned, it is not possible to
attach that new node to the rest of the tree. Such attachment is crucial to the work-
ing of the algorithm.

22. The x = change(x) pattern is an algorithmic strategy by which a recursive
method (such as a binary tree method) will accept a node's initial state as a param-
eter and will then return the node's new state as its result. This returned result will
be stored by the client back into its original place of reference. This technique
allows recursive methods to return modified versions of trees using elegant code
that follows the “zen” of recursion.

23. The contains method is efficient on BSTs and needs to go at most one
direction in each recursive call. Each call advances one level in the tree, so the
total number of calls / advancements is the height of the tree, or N . This
advancement is logarithmic with respect to the total number of nodes in the tree
(its size).

24. This second version of contains is much less efficient than the one written in the
chapter. It goes both to the left and to the right recursively to find the value, but this
does not take advantage of the sortedness of the tree. It will have linear O(N) run-
time rather than the much faster O(log N) desired runtime of our original method.

25. public int min() {
if (overallRoot == null) {
throw new IllegalStateException("empty tree");

}
return min(overallRoot);

}