Flattening a tree with parents/children and return all nodes

Question

It's probably too late, but I can't sleep until it's solved:

I've got a tree with some parents, which have children, which have also children etc.

Now I need a function to get all nodes from the tree.

This is what currently works, but only with one level of depth:

def nodes_from_tree(tree, parent):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child))
    return r

Then I tried to pass r through, so it remembers the children, but I'm using the function more then once and r stores cumulatively all nodes, although I'm setting it to r=[]:

def nodes_from_tree(tree, parent, r=[]):
    r = []
    if len(tree.get_children(parent)) == 0:
        return parent
    for child in tree.get_children(parent):
        r.append(nodes_from_tree(tree, child, r))
    return r

Edit: This is the tree structure:

parent1    parent2    parent3
   |          |          |
   |          |          |
 child        |          |
              |          |
      +--------------+   |
      |       |      |   |
    child   child  child |
      |                  |
  +---+---+              |
child   child        +---+---+
                     |       |
                   child     |
                             |
                       +-----+-----+-----+
                       |     |     |     |
                     child child child child

Available methods:

tree.get_parents()       # returns the nodes of the very top level
tree.get_children(node)  # returns the children of parent or child

how is the tree formated i.e: (value,[(value,[...]),(child2),..])? — HennyH
What is it returning, and what do you expect? (You might want to answer for a much smaller example than the one you pasted as ASCII art…) — abarnert
My guess is that your problem is using append where you meant extend, so you end up returning a list-of-lists tree instead of a flat list. — abarnert
Also, your logic for the parent is wrong. You probably want to do r = [parent] to start with, and then add onto the end of that. (And then you don't need the if statement at all—if there are no children, you won't add anything onto the end, and will just return parent as-is.) — abarnert

abarnert abarnert · Accepted Answer · 2013-05-14T01:07:58

I think your problem is just that you're accumulating things incorrectly.

First, if you hit an intermediate node, each child should return a list, but you're appending that list instead of extending it. So, instead of [1, 2, 3, 4] you're going to get something like [[1, 2], [3, 4]]—in other words, you're just transforming it into a list-of-list tree, not a flat list. Change this to extend.

Second, if you hit a leaf node, you're not returning a list at all, just parent. Change this to return [parent].

Third, if you hit an intermediate node, you don't include parent anywhere, so you're only going to end up with the leaves. But you wanted all the nodes. So change the r = [] to r = [parent].

And with that last change, you don't need the if block at all. If there are no children, the loop will happen 0 times, and you'll end up returning [parent] as-is, exactly as you wanted to.

So:

def nodes_from_tree(tree, parent, r=[]):
    r = [parent]
    for child in tree.get_children(parent):
        r.extend(nodes_from_tree(tree, child, r))
    return r

Meanwhile, while this version will work, it's still confused. You're mixing up two different styles of recursion. Passing an accumulator down the chain and adding to on the way down is one way to do it; returning values up the chain and accumulating results on the way up is the other. You're doing half of each.

As it turns out, the way you're doing the upstream recursion is making the downstream recursion have no effect at all. While you do pass an r down to each child, you never modify it, or even use it; you just create a new r list and return that.

The easiest way to fix that is to just remove the accumulator argument:

def nodes_from_tree(tree, parent):
    r = [parent]
    for child in tree.get_children(parent):
        r.extend(nodes_from_tree(tree, child))
    return r

(It's worth noting that branching recursion can only be tail-call-optimized if you do it in downstream accumulator style instead of upstream gathering style. But that doesn't really matter in Python, because Python doesn't do tail call optimization. So, write whichever one makes more sense to you.)

Flattening a tree with parents/children and return all nodes

2 Answers