From: Intransition <transfire@...>
Date: 2011-07-22T00:21:20+09:00
Subject: Building a tree from the leaves down

Have a algorithmic problem, I can't quite get a clear idea of how to
handle it.

I have a list of objects that respond to `#case` that will return nil
or a case object. Each case object also responds to `#case` and may
return nil or a case object, and so on. Basically I have to build a
tree from the bottom up (top down?) out of this list keyed on cases.

Basic example, let's use this class:

  class CaseObject
    attr :case
    def initialize(parent_case)
      @case = parent_case
    end
  end

And this has been defined:

  c1 = CaseObject.new(nil)
  c11 = CaseObject.new(c1)
  c12 = CaseObject.new(c1)
  c121 = CaseObject.new(c12)
  c122 = CaseObject.new(c12)
  d1 = CaseObject.new(nil)
  d11 = CaseObject.new(d1)
  d12 = CaseObject.new(d1)

Then I am given all the _leaf_ nodes in a list:

  [c11, c121, c122, d11, d12]

I need to reconstruct the hierarchy into a tree (ie. a Hash):

  {
    c1 => {
      c11 => nil,
      c12 => {
        c121 => nil,
        c122 => nil
      }
    },
    d1 => {
      d11 => nil,
      d12 => nil
    }
  }

There's probably some simple way to do this that I am overlooking, but
it's alluding me at the moment.