Exercise 2-25

[Luca]

Hi everyone, I’m stuck on a problem from chapter 2 and I’d like to
solve it before moving on.
Maybe the solution is just there and I can’t see it, so any help is
really appreciated.
The problem is number 2.25 from chapter 2.

“Use cases to write max-interior, which takes a binary tree of
integers (as in the preceding exercise) with at least one interior
node and returns the
symbol associated with an interior node with a maximal leaf sum.”

Now to solve it I think I have to visit every node in the tree and
calculate its leaf sum, this should be done using recursion.
The function max-interior returns a symbol so I can’t see how I could
use its result in a recurvise calculation.
When I read the problem I immediately wrote a function leaf-sum to
calculate the sum of the leaves of any given node, hoping I could use
it inside max-interior, the function is:
(define leaf-sum
(lambda (b)
(cases bintree b
(leaf-node (num) num)
(interior-node (key left right)
(+ (leaf-sum left)
(leaf-sum right))))))

Here is the bintree data type definition:
(define-datatype bintree bintree?
(leaf-node
(num integer?))
(interior-node
(key symbol?)
(left bintree?)
(right bintree?)))

Max-interior should be something like this:
(define max-interior (b)
(cases bintree b
(leaf-node (num) …)
(interior-node (key left right)
…)))

But I can’t move on, I’ve sketched the example trees given in the book
and tried to reason a bit on that but I’m stucked.

Can anyone help?

Thank you,
Luca

[Mitchell Wand]

Try building an intermediate tree?

--
You received this message because you are subscribed to the Google Groups "EOPL3" group.
To post to this group, send email to eo...@googlegroups.com.
To unsubscribe from this group, send email to eopl3+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/eopl3?hl=en.

[Marco Morazan]

> Now to solve it I think I have to visit every node in the tree and
> calculate its leaf sum, this should be done using recursion.

Yes, follow the grammar to guide you in the development of the
recursive function.

> The function max-interior returns a symbol so I can’t see how I could

> use its result in a recursive calculation.

It sounds like you need an auxiliary function that returns something
you need (i.e., not a symbol).

>
> Max-interior should be something like this:
> (define max-interior (b)
>  (cases bintree b
>      (leaf-node (num) …)
>      (interior-node (key left right)
>                     …)))
>

Where is your contract for max-interior? Assuming this function
returns the symbol of the subtree with the max leaf-sum, then it seems
reasonable to compare the leaf-sum of b, the leaf-sum of the
max-interior node of left, and the leaf-sum of the max interior node
in right. Implicit in my hint and described in the problem statement,
is the fact (which should appear in your contract) that max-interior
is always called with a tree that has at least one interior node. In
other words, calling max-interior with a leaf-node should generate an
error.

I hope that helps.

--

Cheers,

Marco

[Luca]

Hi everyone, I guess I solved the problem.
I’ve used an intermediate tree representation.
The general idea is to use “cases” to generate a representation of the
tree that has the symbol and the leaf sum of every interior node, then
I can use this representation to find the symbol associated with the
highest leaf sum value.
So given the tree example in the book, the intermediate representation
is (baz 5 bar 4 foo 5)

*********************************************************************

(define max-interior
(lambda (b)
(car (max-in-list-bintree (bintree-to-list b)))))

(define bintree-to-list
(lambda (b)
(cases bintree b
(leaf-node (num) '())
(interior-node (key left right)
(cons key
(cons (leaf-sum b)
(append (bintree-to-list left)
(bintree-to-list
right))))))))
(define max-in-list-bintree
(lambda (l)
(cond ((null? l) '())
(else
(let ((sym (car l))
(n (cadr l))
(rest (max-in-list-bintree (cddr l))))
(cond
((null? rest) (list sym n))
((> n (cadr rest)) (list sym n))
(else (list (car rest) (cadr rest)))))))))

;;leaf-sum : bintree -> number
(define leaf-sum
(lambda (b)
(cases bintree b

(leaf-node (num) num)
(interior-node (key left right)
(+ (leaf-sum left)
(leaf-sum right))))))

*********************************************************************

I know this could be ugly for you people .. what do you think about
this solution?
Would it be too much to ask for an example of a more elegant and
straightforward solution?

Thank you.

Regards,
Luca