title: turn list of depth first traversal nodes back into tree structure in Ruby
body: <p>Given the following input (from a CSV file):</p>
  
  <pre><code>input = [
    { :level =&gt; 0, :value =&gt; "a"   },
    { :level =&gt; 1, :value =&gt; "1"   },
    { :level =&gt; 1, :value =&gt; "2"   },
    { :level =&gt; 2, :value =&gt; "I"   },
    { :level =&gt; 2, :value =&gt; "II"  },
    { :level =&gt; 2, :value =&gt; "III" },
    { :level =&gt; 0, :value =&gt; "b"   },
    { :level =&gt; 0, :value =&gt; "c"   },
    { :level =&gt; 0, :value =&gt; "d"   },
    { :level =&gt; 1, :value =&gt; "3"   },
    { :level =&gt; 1, :value =&gt; "4"   },
  ]
  </code></pre>
  
  <p>How can I convert this to the following in "The Ruby Way":</p>
  
  <pre><code>expected = [
    { :value =&gt; "a", :children =&gt; [ { :value =&gt; 1, :children =&gt; nil },
                                    { :value =&gt; 2, :children =&gt; [ { :value =&gt; "I", :children =&gt; nil },
                                                                  { :value =&gt; "II", :children =&gt; nil },
                                                                  { :value =&gt; "III", :children =&gt; nil } ] } ] },
    { :value =&gt; "b", :children =&gt; nil },
    { :value =&gt; "c", :children =&gt; nil },
    { :value =&gt; "d", :children =&gt; [ { :value =&gt; 3, :children =&gt; nil },
                                    { :value =&gt; 4, :children =&gt; nil } ] },
    ]
  </code></pre>
  
  <p>?</p>
  
  <p><strong>Edited:</strong></p>
  
  <p>My solution to this was to sidestep the problem, transform it and get someone else to solve it:</p>
  
  <pre><code>require 'yaml'
  def linear_to_tree(a)
    yaml_lines = []
  
    a.each do |el|
      indent = " " * 4 * el[:level]
      yaml_lines &lt;&lt; "#{indent}-"
      yaml_lines &lt;&lt; "#{indent}  :value: #{(el[:value])}"
      yaml_lines &lt;&lt; "#{indent}  :children:"
    end
    yaml_lines &lt;&lt; ""  # without this, YAML.load complains
    yaml = yaml_lines.join("\n")
    # open("test_yaml.txt", "w"){|f| f.write(yaml)}
    YAML.load(yaml)
  end
  </code></pre>
  
  <p>But there must be a more elegant way to solve this.</p>
  
  <p>P.S. I'd also like to see a one-liner for this transformation, just to see if it's possible.</p>