Breadth First Binary Tree Traversal in Scheme

Question

Hello, I am trying to implement a breadth first (level) tree traversal. I'm very close, but I can't figure out how I'm getting duplicates. Any help is much appreciated. Thanks in advance. JR

(define (atom? x)
  (not (pair? x)))

;;Functions to manipulate a binary tree
(define (leaf? node) (atom? node))
(define (left node) (cadr node))
(define (right node) (caddr node))
(define (label node) (if (leaf? node) node (car node)))

;; Breadth First using queue
(define (breadth node)
  (q 'enqueue! node)              ;; Enqueue tree
  (output 'enqueue! (label node)) ;; Output root
  (helper node)
  (output 'queue->list)           ;; Output elements in queue
)
(define (helper node)
    (if (not(q 'empty?))          ;; If queue is not empty
    (begin
       (if(not(leaf? node))
       (begin
          (q 'enqueue! (left node))          ;;  left tree to q
          (output 'enqueue! (label(left node)))   ;; Output root of left tree
          (q 'enqueue! (right node))         ;; Enqueue right tree to q
          (output 'enqueue! (label(right node)))  ;; Output root of right tree
       ))
       (helper (q 'dequeue!))                ;; Dequeues 1st element in q
                                             ;; and recursively calls helper  
    )
    )
)

(define (make-queue)
  (let ((front '())
        (back '()))
    (lambda (msg . obj)
      (cond ((eq? msg 'empty?) (null? front))
            ((eq? msg 'enqueue!) 
             (if (null? front)
                 (begin 
                   (set! front obj)
                   (set! back obj))
                 (begin
                   (set-cdr! back obj)
                   (set! back obj))))
            ((eq? msg 'dequeue!) 
             (begin
               (let ((val (car front)))
                 (set! front (cdr front))
                 val)))
            ((eq? msg 'queue->list) front)))))
(define q (make-queue))
(define output (make-queue))

(define tree '(A (B C D)(E (F G H) I)))

---------------------------------------------------------
Welcome to DrScheme, version 4.2.2 [3m].
Language: R5RS; memory limit: 128 megabytes.
> (breadth tree)
(a b e b e c d f i c d f i g h g h)    ;; Should be (a b e c d f i g h)
>

Answer 1

Since it's homework, I'll just give a hint: rewrite helper to take no arguments.

Answer 2

Thanks so much for the response Mike. So my next question is: How do I initialize the node to a list? I used Let as in (let ((node (q 'dequeue!)) but obviously, the compiler didn't take it. Here's my revised helper.

(define (helper)
(if (not(q 'empty?))
(begin
(let ((node (q 'dequeue!)) ;; Trying to assign the 1st element in list to node ;; Not sure of this line
(if(not(leaf? node))
(begin
(q 'enqueue! (left node))
(output 'enqueue! (label(left node)))
(q 'enqueue! (right node))
(output 'enqueue! (label(right node)))
) ) )) )
(helper) ) ) )