Encode-symbol for Huffman tree
Wouldn't it be easier to unpack the tree into a dictionary mapping each symbol to its corresponding bit string?  Then you could simply look up each symbol in the input to generate the corresponding output bits.

EDIT:
As suggested by syb0rg, here is an implementation (C#, I'm afraid -- my Lisp is far too rusty -- although it's almost pure).  The part pertaining to my suggestion above lives in the HuffmanCodes function at the end.

void Main()
{
    var corpus = @"Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat.";
    var hcs = HuffmanCodes(corpus);
    Console.WriteLine(hcs);
}

Dictionary&lt;char, int&gt; Histogram(string corpus) {
    var hg = new Dictionary&lt;char, int&gt;();
    foreach (var x in corpus) {
        int f;
        hg.TryGetValue(x, out f);
        hg[x] = f + 1;
    }
    return hg;
}

class HuffTree {
    internal char? Sym; // Non-null iff this is a leaf node with no children.
    internal int Freq;
    internal HuffTree L;
    internal HuffTree R;
}

// Oh, for a priority queue.  This is *really* inefficient!
HuffTree HuffmanTree(string corpus) {
    var hg = Histogram(corpus);
    var hts = hg.Keys.Select(x =&gt; new HuffTree { Sym = x, Freq = hg[x] }).OrderBy(t =&gt; t.Freq).ToList();
    while (2 &lt;= hts.Count) {
        var leasts = hts.Take(2).ToList();
        var l = leasts[0];
        var r = leasts[1];
        var newHt = new HuffTree { Freq = l.Freq + r.Freq, L = l, R = r };
        hts = hts.Skip(2).Concat(new HuffTree[] { newHt }).OrderBy(t =&gt; t.Freq).ToList();
    }
    return hts.First();
}

Dictionary&lt;char, string&gt; HuffmanCodes(string corpus) {
    var codes = new Dictionary&lt;char, string&gt;();
    Action&lt;HuffTree, string&gt; a = null; // Sweet recursion.
    a = (ht, code) =&gt; {
        if (ht.Sym != null) {
            codes[(char)ht.Sym] = code;
        } else {
            a(ht.L, code + "0");
            a(ht.R, code + "1");
        }
    };
    a(HuffmanTree(corpus), "");
    return codes;
}