How to create a nested list of parent/child objects using a function?

I'm new to Python and Django and I've encountered a problem I can't solve on my own for quite a long time.

I have a database that consists of a number objects and each object has one parent (except the first, the 'root' object) and no / one / several children. I need to create a fuction that takes some object and returns this object and recursively its descendants like this:

arr = ['States',
       ['Kansas', ['Lawrence', 'Topeka', ['Some Topeka Street', ['Some House on Some Topeka Street']]],
        'Illinois', ['Chicago', 'Springfield']]]

I want to get this kind of data structure and use it on Django's unordered list filter.

As far as I know about algorithms I should make up a function that somehow should work like this:

def make_nested_list(item):
    if not item.children: # basic case
        # do something
    else:
        for child in item.children: # recursive case
            # do something
            make_nested_list(child) # function calls itself
    # maybe do something here
    # and finally return self-nested list
    return result 

Everything I try turns out to be a mess. How can I do that?

Assuming that your item objects have name attributes, here is what you could do:

def list_nodes(siblings):
    for node in siblings:
        yield node.name
        if node.children:
            yield list(list_nodes(node.children))

So the argument to this function is a list of nodes. If you just have one root object, then first put it in a list, and pass that as argument:

result = list(list_nodes([root]))

Here is the test I performed, which includes the creation of mock data:

from collections import namedtuple

Node = namedtuple("Node", "name, children")

root = Node("States", [
    Node("Kansas", [
        Node("Lawrence", []), 
        Node("Topeka", [])
    ]), 
    Node("Illinois", [])
])

print(root)

def list_nodes(siblings):
    for node in siblings:
        yield node.name
        if node.children:
            yield list(list_nodes(node.children))

result = list(list_nodes([root]))

print(result)

This outputs (with some formatting applied):

Node(name='States', children=[
    Node(name='Kansas', children=[
        Node(name='Lawrence', children=[]), 
        Node(name='Topeka', children=[])
    ]),
    Node(name='Illinois', children=[])
])

['States', ['Kansas', ['Lawrence', 'Topeka'], 'Illinois']]
Back to Top