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.

Answer 2

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

function f(root, find)
    -- iterate over all child values
    for k, v in pairs(root) do
        if k == find then
            -- found the match
            return({find})
        else
            -- no match, search the children
            tmp = f(root[k], find)
            if tmp ~= nil then
                table.insert(tmp, 1, k)
                return tmp
            end
        end
    end
end

print(table.concat(f(A, "G"), " "))

since you cannot retrieve the name of the highest-order table (in this case, A), you might need to nest this table into another table as in the following example:

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

in this case, you will need to call f(r, "G"), of cause.

Answer 3

This is the solution I came up with with using Dario's advice:

function checkTable(t, key)
    if t[key] then
        return {key}
    else
        for k, subtable in pairs(t) do
            local children = checkTable(subtable,key)
            if #children ~= 0 then
                table.insert(children,1,k)
                return children
            end
        end
        return {}
    end
end

Answer 4

If there are loops in the hierarchy, you'll need to keep track of visited subtables. See the globals code in the Lua live demo.