python - Flattening a tree with parents/children and return all nodes -

it's late, can't sleep until it's solved:

i've got tree parents, have children, have children etc.

now need function nodes tree.

this works, 1 level of depth:

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

then tried pass r through, remembers children, i'm using function more once , r stores cumulatively nodes, although i'm setting r=[]:

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

edit: tree structure:

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

available methods:

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

i think problem you're accumulating things incorrectly.

first, if hit intermediate node, each child should return list, you're appending list instead of extending it. so, instead of [1, 2, 3, 4] you're going [[1, 2], [3, 4]]—in other words, you're transforming list-of-list tree, not flat list. change extend.

second, if hit leaf node, you're not returning list @ all, parent. change return [parent].

third, if hit intermediate node, don't include parent anywhere, you're going end leaves. wanted nodes. change r = [] r = [parent].

and last change, don't need if block @ all. if there no children, loop happen 0 times, , you'll end returning [parent] as-is, wanted to.

so:

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

---

meanwhile, while version work, it's still confused. you're mixing 2 different styles of recursion. passing accumulator down chain , adding on way down 1 way it; returning values chain , accumulating results on way other. you're doing half of each.

as turns out, way you're doing upstream recursion making downstream recursion have no effect @ all. while pass r down each child, never modify it, or use it; create new r list , return that.

the easiest way fix remove accumulator argument:

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

(it's worth noting branching recursion can tail-call-optimized if in downstream accumulator style instead of upstream gathering style. doesn't matter in python, because python doesn't tail call optimization. so, write whichever 1 makes more sense you.)