title: Breadth First Binary Tree Traversal in Scheme
body: <p>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</p>
  
  <pre><code>(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-&gt;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-&gt;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.
  &gt; (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)
  &gt;
  </code></pre>