[LRUG] Pruning a tree

[Andrew Stewart]

Hola El Rug,

I have a tree about 10 levels deep with ~600k nodes in all.  An offline process identifies about ~100 different nodes in the tree.

I would like to prune the tree such that the only nodes left are the identified ones and the ones connecting them back to the root.  We ignore any children of identified nodes.  Ideally the result would be a hash of nested hashes/arrays.

For example, given the following tree (only relevant parts shown) with identified nodes a, b, d, z:

root -> x -> a
root -> x -> y -> b
root -> x -> y -> c -> d
root -> z

I would like this result:

root => [
          {x => [
                   a,
                   y => [
                          b,
                          {c => d}
                        ]
                 ]
          },
          z
        ]

As a bonus, each identified node has a count associated with it.  I would like to sum the counts along the way from the node to the root.  So, in the example, y's calculated count = b's + d's.

My attempts have revolved around recursively merging hashes but I can't seem to get it quite right...

Yours,
Andy Stewart

-------
http://airbladesoftware.com