Do I misunderstand the meaning of exercise 2.65 of SICP?

Question

Here is the exercise 2.65 of SICP:

Use the results of exercises 2.63 and 2.64 to give Θ(n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

In the chapter "Sets as ordered lists" and exercise 2.62, we already have the union-set and intersection-set for the ordered lists. I have searched the Internet, the answer of 2.65 is too simple to accept, they just convert the binary trees into lists and still use the the union-set and intersection-set for the ordered lists.

In my opinion, we need to convert the sets into binary trees and rewrite the union-set and intersection-set for the binary trees.

So, do I misunderstand the meaning of exercise 2.65 of SICP? Or is there a good answer?

Answer 1

The "simple" answer is correct in this case: the exercise is solved by first converting the trees into lists (in fact, ordered lists because we're doing inorder traversal of the trees), then using ordered-set procedures, and finally converting the resulting sets back into trees. Why is this correct? because the procedure described achieves the required O(n) complexity using already-existing procedures - no need to reinvent the wheel!

Although a "direct" answer can be written by manipulating trees, it's too much of a hassle, and it'll be very tricky (if not impossible!) to implement in O(n) without using mutation operations - and up to this point in the book, we have not yet used set!, set-car! or set-cdr!.

Answer 2

You're right, you could use earlier examples from the text as a guide to writing efficient implementations of union-set and intersection-set for balanced binary trees. However, the text explicitly tells you to use the results from the two previous exercises, so it's guiding you towards a particular solution. That solution (convert the binary tree to a list to reduce the problem to one already solved) is already O(n), which is the best order you can get with this problem anyway.