How can I write a function that returns a list of keys in a nested table?

Question

I have a hierarchically nested associative array. It looks like this:

A = { 
    B = { 
        C = {}, 
        D = {}, 
    }, 
    E = { 
        F = { 
            G = {} 
        } 
    }, 
    H = {} 
}

I would like to write a function that returns the "ancestors" of each key.

So:

f("A") = {"A"} 
f("B") = {"B","A"} 
f("C") = {"C","B","A"} 
f("G") = {"G","F","E","A"} 
f("fake") = {} 

I've worked out I need to use recursion, but I'm having difficulty writing the function. Could someone give me some pointers on how to write such a function?

(Please don't refer me to http://xkcd.com/138/!)

Answer 1

Just apply a recursive depth-first search to find your specific element and return the path.

Recursive steps to construct path for element X.

• If current element is X: return {X}

• If current element is not X:

  1. Check all child nodes.
  2. Get the child-node that returns a valid path and add current element to it.
  3. If there is no valid child-node, return nil.