「リンゴ列をもっと短く！」のやり直し

CodeIQで id:hyuki さんが出題された「リンゴ列をもっと短く！」を解いてみたのですが、

でした…。ちょっと自信があったつもり(?)だったので、結果を見て残念なのですが、復習が肝心と思い、朝から何がまずかったのか考えてみました。
まず、致命的なミスは、以下の注意を怠った点です。解答より引用しています。

ここで注意が必要なのは、今回のリンゴ問題では文字の種類が26（偶数）だということです。そのため、出現頻度の低い方から3個のノードをまとめて親ノードを作っていくと、最後（の一歩手前）に列に残るのは（3個ではなく）2個のノードになってしまいます。そうすると、リンゴ列の割り当てに無駄が生じ、結果としてリンゴ列を長くしてしまいます。

これを解決するため、最後（の一歩手前）に列に残るノードを3個のノードにします。「出現頻度が0のダミー文字」を用意し、これを列に並べておくのです（結果的に27個の文字から始めることになります）。このようにすれば、無駄なく3分木によるハフマン木を構築することができます。

上記については、問題を解くときに全く気づいていなかったので、「あっ、なるほど！」という間違えても爽快感があるのですが、ちょっと悔しく思うのは、ハフマン木を構築したあと、木をトラバースする処理に致命的な凡ミスがあって、それを気づかず解答してしまったことが非常に情けなく思います。まだまだ修行が足りません。
恥ずかしいですが、自分の解答を載せます。コメントに"追加"とあるのが、今朝、修正した部分です。

apple.rb

# -*- coding: utf-8 -*-
class Node
  attr_accessor :freq, :left, :center, :right
  def initialize(freq, left = nil, center = nil, right = nil)
    @freq = freq
    @left, @center, @right = left, center, right
  end
end

class Leaf < Node
  attr_accessor :ch
  def initialize(ch, freq)
    @ch, @freq = ch, freq
  end
end

typical_text = File.open('typical.txt').read
freq = Hash.new(0)
# 各単語の出現頻度を調べる
typical_text.each_char {|ch|
  freq[ch] += 1
}

freq[""] = 0                    # 追加：出現頻度0のダミー文字(あっ、なるほど！のミス)
arr = []
freq.each {|k, v|
  arr << Leaf.new(k, v)
}
loop {
  break if arr.size == 1
  arr.sort_by!{|e| e.freq }
  if arr.size == 2
    l = arr.shift
    c = arr.shift
    arr << Node.new((l.freq+c.freq), l, c)    
  else
    l = arr.shift
    c = arr.shift
    r = arr.shift
    arr << Node.new((l.freq+c.freq+r.freq), l, c, r)
  end
}

$path = ""              
$ans = Hash.new

def traverse node, code = nil
  $path << code unless code.nil?
  if node.instance_of?(Leaf)
    $ans[node.ch] = $path.dup
    $path.slice!(-1)
    return
  end
  traverse node.left, "r"   unless node.left.nil?
  traverse node.center, "g" unless node.center.nil?
  traverse node.right, "b"  unless node.right.nil?
  $path.slice!(-1)              # 追加：情けないミス…
end

traverse arr.first
$ans.sort.each {|ele|
  puts "#{ele[0]}:#{ele[1]}" unless ele[0] == "" 
}