(define (encode message tree)
(if (null? message)
'()
(append (encode-symbol (car message) tree)
(encode (cdr message) tree))))
(define (encode-symbol message tree)
(if (leaf? tree)
'()
(if (memq message (symbols (left-branch tree)))
(cons 0 (encode-symbol message (left-branch tree)))
(cons 1 (encode-symbol message (right-branch tree))))))
(define (encode-symbol message tree)
(define (iter m t bits)
(if (leaf? t)
(reverse bits)
(if (memq m (symbols (left-branch t)))
(iter m (left-branch t) (cons 0 bits))
(iter m (right-branch t) (cons 1 bits)))))
(iter message tree '()))
(let ((msg '(A D A B B C A)))
(equal? msg (decode (encode msg sample-tree) sample-tree)))