CODEWITHSUNDEEP
pythonrecursiontree
Tom Carrick
Tom Carrick

Reputation: 6616

Recursive function for trees in Python

I'm trying to make a function in Python, that takes an arbitrary node of a tree, and populates a list of lists based on the node give.

Given the following badly drawn tree:

Tree

If we start at, for example, node 5, we should get:

And the nodes should end up in a list of lists, one list for each depth.

The nodes in python:

nodes = [
    {'id': 1, 'parent': None},
    {'id': 2, 'parent': 1},
    {'id': 3, 'parent': 1},
    {'id': 4, 'parent': 2},
    {'id': 5, 'parent': 2},
    {'id': 6, 'parent': 5},
    {'id': 7, 'parent': 6},
    {'id': 8, 'parent': 3}
]

We can only see parents, not children, but this is the data format I have to work with, sadly.

So from this, if we take node 5, we want to end up with a node list looking something like this:

nl = [
    [{'id': 6, 'parent': 5}],
    [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}],
    [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}],
]

This is the code I have so far. I figure a recursive function is probably the simplest way. Unfortunately it seems to do nothing like what I think it should, and obviously I'm doing something very wrong. And this code doesn't even consider geting the child nodes which I'm not entirely sure how to deal with at all, apart from possibly handing the afterwards which would be much easier.

node_list = []

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            parent = node['parent']
    return pop_list(nodes, parent, node_list)

print pop_list(nodes, 5, node_list)

Here is the output:

[[], [{'id': 3, 'parent': 1}], []]

Not exactly sure where I'm going wrong here.

Upvotes: 13

Views: 32686

Answers (2)

Lalit Sangtani
Lalit Sangtani

Reputation: 1

def processNode(bp, space=''):
    if ('name' in bp[0].keys() ):
        print( space + bp[0]['name'])
    if ('subNodesTitle' in bp[0].keys()):
        print( bp[0]['subNodesTitle'])
        processNode( bp[0]['subNodes'],space=space+' ')
    if (len(bp) > 1):
        processNode( bp[1:],space=space )
processNode(root)

This function can recurse through an unbalanced tree,

Upvotes: 0

nymk
nymk

Reputation: 3393

The problem is here

    if node['id'] == parent:
        parent = node['parent']

The current parent will be overwritten by its parent.

Moreover, you should add return node_list at the end of the function, or use node_list as results.

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            next_parent = node['parent']

    pop_list(nodes, next_parent, node_list)
    return node_list

>>> print pop_list(nodes, 5, node_list)
[[{'id': 6, 'parent': 5}], [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}], [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}]]

Upvotes: 7

Related Questions