[plt-scheme] Excersise 14.2.3 - HtDP - Ordered list of binary tree nodes

From: Marco Morazan (morazanm at gmail.com)
Date: Fri Feb 20 08:51:55 EST 2009

> As you'd expect, it's just a listing of all the nodes. I'm clueless as
> to how I can order them left-to-right.

It is actually listing the values that you want in pre-order which is
different from in-order (and post-order).

> The useless function I have which just lists nodes at the moment is as follows:
> (define (inorder bt)
>  (cond
>    [(false? bt) empty]
>    [else (cons (node-ssn bt) (append (inorder (node-left bt))
>                                                     (inorder
> (node-right bt))))])
>> (inorder a-BT)
> (list 63 29 15 10 24 89 77 95 99)

Your problem is that you are only *partially* following the design
recipe. Your function has the right structure based on the structure
of a BT. However, the design recipe also calls for you to create
examples and to carefully think about how to combine the values of the
recursive calls with the the parts of bt of interest to you. These two
essential steps are what you have not done.

I strongly suggest you start by thinking about simple examples before
jumping head-first into an example like your a-BT.

Start by asking yourself:

(inorder false) = ???
(inorder (make-node 10 'e false false)) = ???
(inorder (make-node 89 'g (make-node 77 'h false false) (make-node 95
'i false false))) = ???

These simple examples should give you insight into how the values
obtained from the recursive calls should be combined with the ssn of

Finally, to be able to exploit the insights that the examples will
give you it is necessary to have a clear idea of what kind of value
the function inorder returns. Since you did not exhibit your contract,
we do not know if you have that clear idea. I strongly suggest you
first figure out the contract for inorder if you have not already done
so. The hint to use append is not just a random suggestion.




Posted on the users mailing list.