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

user_8142713 0
Viewed 76

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

computer-science
3 Answers

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"]}
user_4770370 
def explore_tree(tree, names=[])
  names = [tree[:name]] + names
  if tree[:children].empty?
    p names
  else
    tree[:children].each { |child| explore_tree(child, names) }
  end
end

explore_tree(tree)

displays

["grand_child1", "child1", "root"]
["grand_child2", "child1", "root"]
["child2", "root"]
user_2569700 
def get_paths(hash)
  # Stop method and return name if name is address
  return hash[:name] if hash[:children].empty?
  paths = [] # Declaring path variable
  # Inspecting children
  hash[:children].each do |child|
    child_paths = get_paths(child)
    if child_paths.is_a? String
      paths << [child_paths, hash[:name]]
    else
      child_paths.each { |path| path << hash[:name] }
      paths += child_paths
    end
  end
  paths # Return paths
end

p *get_paths(tree).map { |path| path.to_s[1..-2] }
# => "grand_child1", "child1,", "root"
# => "grand_child2", "child1,", "root"
# => "child2", "root"
user_78961070
Related