http://pastebin.com/U3W6z4XJ

z2.rb

class BinaryTree
  attr_accessor :root

  def initialize
    @root = Node.new
  end

  def insert(letter, path)
    node = root
    path.each_char do |direction|
      node = node.public_send(direction)
    end
    node.letter = letter
  end
end

class Node
  include Enumerable

  attr_accessor :letter, :parent
  attr_writer :l, :r
  def initialize(parent = nil, letter = nil)
    @parent = parent
    @letter = letter
  end

  def l
    @l ||= Node.new(self)
  end

  def l?
    !@l.nil?
  end

  def r
    @r ||= Node.new(self)
  end

  def r?
    !@r.nil?
  end

  def each(&block)
    l.each(&block) if l?
    block.call(self)
    r.each(&block) if r?
  end

  def <=>(other_node)
    return -1 if l? || r?
    word <=> other_node.word
  end

  def to_s
    word
  end

  def word
    parent.nil? ? letter : letter + parent.word
  end
end

tree = BinaryTree.new
begin
  while (input = gets.chomp)
    letter, path = input.split
    next if letter.nil?
    path ||= ""
    tree.insert(letter, path.downcase)
  end
rescue Interrupt
  puts tree.root.max.word
end

to run:
$ ruby z2.rb
input:

a LL
d 
a R
s L
ctrl-c
=> ASD