How to take keys within hash objects

Question

hash = {
  "d" => {
    "o" => {
      "g" => {
        "s" => {}
      },
      "l" => {
        "l" => {}
      },
      "o" => {
        "m" => {}
      }
    }
  },
  "b" => {
    "o"=>{
      "o"=>{
        "m"=>{}
      }
    }
  }
}

trie.print(hash)

Within the Trie class there is method called print to print trie:

def print(trie)
  trie.each do |k,v|
    @res.concat(k)
    print(trie[k]) if trie[k].length > 0
    unless trie[k].length > 0 
      @result << @res unless trie[k].length > 0
      @res = ""
      p @result 
    end
  end
end

The above method prints:

["dogs", "ll", "om", "boom"]

But I want to print:

["dogs" , "doll", "doom" , "boom"]

Answer 1

I've renamed the function to compose to avoid clashing with Kernel#print. The reason for that is that I'm calling this function from the inside, where it should be callable without pointing to an object explicitly. The approach you're using doesn't "reuse" traversed prefixes. The most common way to do this is to use recursion and build up that prefix in the arguments.

I've got this recursive function. Recursion is a common approach to processing trees. It accepts a "subtrie" and a prefix it's placed below (defaults to empty string, if none given). Recursion base: if we got an empty subtrie, we return a single-element array of a built up prefix at this point. Higher levels will return arrays of prefixes built from a given "subtrie".

def compose(trie, prefix="")
  trie.flat_map do |k, v|
    new_prefix = prefix + k
    results = compose(v, new_prefix)
    results.empty? ? new_prefix : results
  end
end

Note flat_map, otherwise (with map) it will output a deeply nested array structured as your trie with leaves replaced with built up prefixes.

UPD: the new version returns an empty array for empty subtrie.