CODEWITHSUNDEEP
pythonrecursiontree
dave
dave

Reputation: 7867

Trying to come up with a recursive function to expand a tree in Python

I have table that looks like this:

id  | parentid | name
---------------------
 1  |    0     | parent1
---------------------
 2  |    0     | parent2
---------------------
 3  |    1     | child1
---------------------
 4  |    3     | subchild1

I'm now trying to come up with an efficient way to take that database data and create a Python dictionary.

Basically, I want to be able to do:

tree = expand(Session.query(mytable).all())
print tree['parent2']['child2']

# result would be 'subchild1'

I'm at a complete loss with how to do this... I've been messing around with the following function but I can't get it working. Any help would be appreciated.

def expand(tree):

   parents = [i for i in tree if i.parentid == 0]

   for parent in parents:
      children = expand(parent)

Upvotes: 1

Views: 2198

Answers (2)

Eric Fortin
Eric Fortin

Reputation: 7603

If I understand correctly, the item for which their parent id is 0 are the root one or the first level ?

If so, your method should look like:

def expand(tree, id):
    expanded_tree = {}

    parents = [i for i in tree if i.parentid == id]

    for parent in parents:
        expanded_tree[parent.name] = expand(tree, parent.id)

    return expanded_tree

and you'd start it like:

tree = expand(Session.query(mytable).all(), 0)

Upvotes: 2

Jochen Ritzel
Jochen Ritzel

Reputation: 107736

Your example doesn't match the data given but this should be what you want.

It's not recursive, because recursion does not make sense here: The input data has no recursive structure (that's what we are creating), so all you can write as a recursion is the loop ... and that is a pretty pointless thing to do in Python. 

data = [ (1,0,"parent1"), (2,0,"parent2"), (3,1,"child1"), (4,3,"child2")]

# first, you have to sort this by the parentid
# this way the parents are added before their children
data.sort(key=lambda x: x[1])

def make_tree( data ):
    treemap = {} # for each id, give the branch to append to
    trees = {}
    for id,parent,name in data:
        # {} is always a new branch
        if parent == 0: # roots
            # root elements are added directly
            trees[name] = treemap[id] = {}
        else:
            # we add to parents by looking them up in `treemap`
            treemap[parent][name] = treemap[id] = {}

    return trees

tree = make_tree( data )
print tree['parent1']['child1'].keys() ## prints all children: ["child2"]

Upvotes: 1

Related Questions