Hello,

I should probably warn you that this is a homework question, but I have tried to solve it, honestly.

"Construct a program that outputs (in some order) all structurally distinct binary trees of n nodes. Two trees are considered structurally distinct if they have different numbers of nodes or if their left or right subtrees are structurally distinct."

Here's my attempt,

(define-struct tree (left right))

;; trees : Integral -> (ListOf Tree)
;; Return a list of all structurally distinct binary trees containing
;; N nodes.
(define (trees N)
  (cond ((< N 1) empty)
        ((= N 1) (make-tree empty empty))
        (else
         (map (lambda (root)
                (let ((left-tree  (trees (- root 1)))
                      (right-tree (trees (- N 1 root))))
                  (make-tree left-tree right-tree)))
              (build-list N add1)))))

I'm ashamed to point out that my function doesn't comply with my contract. That's my problem: I end up inserting lists of trees instead of structures into my tree's children. I can't see a away to avoid making a list in the recursive calls, though.

I'm all tangled up with this. Can anyone help me out?

Thanks,
Damien.
_________________________________________________
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/users

Reply via email to