Given a 'tree' like data structure, print out all the paths from leaf to root

Question

Could somebody guide me in the right direction with this please, I don't understand how to return the results from leaf to root

tree = {
    "name": "root",
    "children": [
        {
            "name": "child1",
            "children": [
                {
                    "name": "grand_child1",
                    "children": []
                },
                {
                    "name": "grand_child2",
                    "children": []
                }
            ]
        },
        {
            "name": "child2",
            "children": []
        }
    ]
}

EDIT: The solution should be an algorithm, in that if tree depth is increased it should still work

Answer 1

You could use recursion, e.g:

def traverse(node, *names, &block)
  names.unshift(node[:name])

  yield *names and return if node[:children].empty?

  node[:children].each { |child| traverse(child, *names, &block) }
end

The method operates on a single node. On each invocation, it adds the node's name to a list of gathered names (initially empty). It then calls itself again for each child, passing names. If a node doesn't have any children, it yields names to the given block. (which is passed along too)

Usage:

traverse(tree) do |*names|
  p name: names
end

Output:

{:name=>["grand_child1", "child1", "root"]}
{:name=>["grand_child2", "child1", "root"]}
{:name=>["child2", "root"]}