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

From: Charlie Turner (charlie.h.turner at googlemail.com)
Date: Fri Feb 20 15:54:07 EST 2009

The design recipes are fine, but it's the theory of ordering these
nodes that I don't understand. I'm sorry for not posting my full
Design Recipe,

;; inorder : BT -> list
;; to ouput the nodes of BT in an order of
;; left to right

;; Examples
 ; (inorder false) -> empty

 ; (inorder (make-node 1 'a false false)) -> (list 1)

 ; (inorder (make-node 1 'a (make-node 2 'b false false) (make-node 3
'c false false false)))
;   -> (list 2 1 3)

 ; (inorder (make-node 1 'a (make-node 2 'b (make-node 3 'c false false)
;                                           (make-node 4 'd false false))
;                           (make-node 5 'e (make-node 6 'f false false)
;                                           (make-node 7 'g false false))))
;   -> (list 3 2 4 1 6 5 7)

;; Template
; (define (inorder BT)
;   (cond
;     [(false? BT) ...]
;     [else (... (node-ssn BT) ...)
;           (... (inorder (node-left BT)) ...)
;           (... (inorder (node-right BT)) ...)]))

Maybe the template is whats getting me into trouble. I struggle on
occasion to decide where I should put the "natural recursions".

Marco. Thank you for your input. I tried very hard to see how these
examples exploded into the bigger picture, I just couldn't find a
recursion that did what I wanted.

David. I don't know what (inorder (node-left BT)) should do and I
believe what Veer said has a lot of truth, in that I really just don't
understand how to navigate these tree's (I haven't looked at the link
as instructed!). I have a vision that I should keep on checking
(node-left bt) until it becomes false, and them I'm at the start of
the list I want. However, when I try to crawl back across the right, I
just get stuck, and my list just end ups with one or two items from
the lowest left "triangle".

I just don't see a way of not getting stuck underneath the
branches(?). From the data definition, it would appear to me that you
have to stay at the top of the tree and do all the work, but I don't
see how.

Matthias. I hope my fuller definition above will reveal the problems
in my understanding of this question.

I really appreciate the input I'm receiving.

Charlie Turner.

Posted on the users mailing list.