Python: Algorithm Traverse Tree that expands at each node

Question

I have a dictionary with id and multiple values for each ID which are strings. For each value in that for each Id I make a database query and get set results:

{111: Run, Jump, swim}
{222: Eat, drink}

so for each value lets say run I execute a query and it returns another set of data then pick each value of that set and run query which will give another set and finally I come to a point where there is only one item get return. Once I finish get that final element of every single sub element of Run then I move to Jump and continue.

I asked this question before but didn't get any results so people told me to remove the code and just ask the question again. Here is the link for the same question which I ask few days ago. Do i need to implement something like disjoin set?

Answer 1

You can look at the categories/subcategories as a tree with N branches at each node (depending how many categories you have). From what I can gather you basically want to generate an in-order list of tree leaves.

One simple way of doing it is through generators (using the terminology from your original question):

def lookup(elem):
    # do your SQL call here for a given category 'elem' and return
    # a list of it's subcategories
    return []

def leaves(lst):
    if lst:
        for elem in lst:                          # for every category
            for sublist in leaves(lookup(elem)):  # enumerate it's sub categories
                yield sublist                     # and return it
            yield elem                            # once lookup(elem) is [] return elem

d = { 111: [Run, Jump, swim] , 222: [Eat, drink] }

for key, lst in d.items():
    print key, [elem for elem in leaves(lst)]

If you are unfamiliar with generators, they are simply iterator constructs that "yield" values instead of returning them. The difference is that yielding only pauses the iterator at that location which will continue where it stopped when the next value is requested.

With some clever recursion inside the generator you can simply parse the whole tree.

The [elem for elem in leaves(lst)] is a list comprehension and it simply builds a list containing elem for every element iterated by leaves.

Answer 2

This looks like plain tree traversal. You can use BFS or DFS.