I'd go with something like this:

def find_node_path(tree, search_key)
  return unless tree.is_a?(Hash)
  return [] if tree.key?(search_key)

  tree.each do |key, node|
    path = find_node_path(node, search_key)
    return [key, *path] if path
  end

  nil
end

path = find_node_path(tree, :a30)
#=> [:a00, :a11, :a22]

# retrieve value
value = tree.dig(*path, :a30)
#=> {}

This does the following, it returns nil if the current tree is not an hash, or if the search_key cannot be found in the current tree structure.

The method loops through all key/value-pairs of the hash, calling find_node_path recursively. If nil is returned it denotes that the search_key can't be found, thus jumping to the next iteration in the loop.

If the return value is not nil it means that the search_key is found at path in node relative to the tree. In this scenario, prepend the path with the key of the current iteration and return it.

Note: Although this solution does work if search_key is not unique in the structure. It will only return the first match found. Since this solution uses depth first it would return [:a1, :a2] when tree = {a1: {a2: {a3: {}}}, b1: {a3: {}}} for search_key = :a3.

Code

def extract(h,target_key)
  return [target_key, h[target_key]] if h.key?(target_key)
  h.each do |kk,v|
    next unless v.is_a?(Hash)
    arr = extract(v,target_key) 
    return [kk,*arr] unless arr.nil?
  end
  nil
end

Example

h = {
  :a00=>{
    :a10=>{
      :a20=>{1=>2}, 
      :a21=>{3=>4}
    }, 
    :a11=>{
      :a22=>{
        :a30=>{5=>6}, 
        :a31=>{7=>8}
      }
    }
  }
}

[:a00, :a10, :a20, :a21, :a11, :a22, :a30, :a31, 3, :a32].each do |k|
  puts ":#{k} -> #{extract(h,k) || "nil"}"
end

target_key -> extract(h, target_key)

:a00 -> [:a00, {:a10=>{:a20=>{1=>2}, :a21=>{3=>4}},
                :a11=>{:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}}]
:a10 -> [:a00, :a10, {:a20=>{1=>2}, :a21=>{3=>4}}]
:a20 -> [:a00, :a10, :a20, {1=>2}]
:a21 -> [:a00, :a10, :a21, {3=>4}]
:a11 -> [:a00, :a11, {:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}]
:a22 -> [:a00, :a11, :a22, {:a30=>{5=>6}, :a31=>{7=>8}}]
:a30 -> [:a00, :a11, :a22, :a30, {5=>6}]
:a31 -> [:a00, :a11, :a22, :a31, {7=>8}]
:3   -> [:a00, :a10, :a21, 3, 4]
:a32 -> nil

Explanation

In my experience the only useful way to explain how a recursive method works is to show the result of salting the method with puts statements and running an example. Moreover, to keep things straight when examining the output it's necessary to indent the output each a method calls itself and "undent" the output whenever the method returns. I've done that below for my method extract. It requires time and patience to go through the calculations that are performed, but anyone doing so should gain a solid understanding of how this method works, and perhaps also learn something about recursive methods generally. There's no need, of course, to understand the code below that displays the calculations that are performed.

INDENT = 6
$col = 4-INDENT
def indent
  $col += INDENT
end
def undent
  $col -= INDENT
end
def prn
  print " "*$col
end
def divide
  puts "#<p></p>"
end

def extract(h,target_key)
  divide
  indent
  prn; puts "entering extract"
  prn; puts "h=#{h}"
  prn; puts "h.key?(#{target_key}) = #{h.key?(target_key)}"
  if h.key?(target_key)
    prn; puts "returning #{[target_key, h[target_key]]}"
    undent
    divide
    return [target_key, h[target_key]]
  end
  h.each do |kk,v|
    prn; puts "  kk=#{kk}"
    prn; puts "  v=#{v}"
    prn; puts "  v.is_a?(Hash) = #{v.is_a?(Hash)}"
    prn; puts "  skip key" unless v.is_a?(Hash)  
    next unless v.is_a?(Hash)
    prn; puts "  call extract(#{v},target_key)"
    arr = extract(v,target_key)
    prn; puts "  arr=#{arr.nil? ? "nil" : arr} returned"
    if arr
       prn; puts "  target key found"
       prn; puts "  returning [#{[kk,*arr]}]"
       undent
       divide  
       return [kk,*arr]
    end
  end
  prn; puts "returning nil"
  undent
  divide 
  nil
end

extract(h,:a30)

entering extract
h={:a00=>{:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}}
h.key?(a30) = false
  kk=a00
  v={:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}
  v.is_a?(Hash) = true
  call extract({:a10=>{:a20..., :a31=>{7=>8}}}},target_key)

      entering extract
      h={:a10=>{:a20=>{1=>2},...,:a31=>{7=>8}}}}
      h.key?(a30) = false
        kk=a10
        v={:a20=>{1=>2}, :a21=>{3=>4}}
        v.is_a?(Hash) = true
        call extract({:a20=>{1=>2}, :a21=>{3=>4}},target_key)

            entering extract
            h={:a20=>{1=>2}, :a21=>{3=>4}}
            h.key?(a30) = false
              kk=a20
              v={1=>2}
              v.is_a?(Hash) = true
              call extract({1=>2},target_key)

                  entering extract
                  h={1=>2}
                  h.key?(a30) = false
                    kk=1
                    v=2
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
              kk=a21
              v={3=>4}
              v.is_a?(Hash) = true
              call extract({3=>4},target_key)

                  entering extract
                  h={3=>4}
                  h.key?(a30) = false
                    kk=3
                    v=4
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
            returning nil

        arr=nil returned
        kk=a11
        v={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
        v.is_a?(Hash) = true
        call extract({:a22=>{:a30..., :a31=>{7=>8}}},target_key)

            entering extract
            h={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
            h.key?(a30) = false
              kk=a22
              v={:a30=>{5=>6}, :a31=>{7=>8}}
              v.is_a?(Hash) = true
              call extract({:a30=>{5=>6},
                :a31=>{7=>8}},target_key)

                  entering extract
                  h={:a30=>{5=>6}, :a31=>{7=>8}}
                  h.key?(a30) = true
                  returning [:a30, {5=>6}]

              arr=[:a30, {5=>6}] returned
              target key found
              returning [[:a22, :a30, {5=>6}]]

        arr=[:a22, :a30, {5=>6}] returned
        target key found
        returning [[:a11, :a22, :a30, {5=>6}]]

  arr=[:a11, :a22, :a30, {5=>6}] returned
  target key found
  returning [[:a00, :a11, :a22, :a30, {5=>6}]]

  #=> [:a00, :a11, :a22, :a30, {5=>6}]