Python output a list in hierarchy

Question

I've been trying to write a recursive function for the below code example but the issue im facing is that my loop gets double up in value the next time I run it.


def get_choices():
    choices = []
    nodes = Node.query.filter_by(parent_id=None).all()
    for node in nodes:
        choices.append((node.id, f"{node.value}"))
        if node.children:
            for child in node.children:
                choices.append((child.id, f"-{child.value}"))
                if child.children:
                    for c in child.children:
                        choices.append((c.id, f"--{c.value}"))

    return choices

the code im currently working on


def get_choices():
    c = Node.query.filter_by(parent_id=None).all()

    return _get_choices(c)

def _get_choices(children, depth=0, prev_choices=[]):

    new_choices = prev_choices
    for child in children:
        new_choices.append((child.id, f"{depth * '-'}{child.value}"))
        if child.children:
            _get_choices(child.children, depth+1, new_choices)
    
    return new_choices

Thank you so much, it helped me solve my problem. – Dec 27 '21 at 00:39 — , Dec 27 '21 at 00:39

Grismar · Accepted Answer · 2021-12-27T00:43:33.517

I think you were going for something like:

def _get_choices(nodes, depth=0):
    if not nodes:
        return []
    for node in nodes:
        yield (node.id, f"{depth * '-'}{node.value}")
        yield from _get_choices(node.children, depth+1)


def get_choices():
    return list(_get_choices(Node.query.filter_by(parent_id=None).all()))

I don't know what to expect in Node exactly, but if my understanding of your data structure is correct, this will yield a tuple for each node and each of its children, all the way down, depth first.

By the way: it's generally not a good idea to use the name of built-in functions or keywords as variable or attribute names. It works just fine, but you probably want to rename id (which is a built-in function).

Since I didn't have data to test, here's an example that does the same with sample data:

class Node:
    def __init__(self, ident, value, children=None):
        self.ident = ident
        self.value = value
        self.children = children if children else []


data = [
    Node(1, 'a', [Node(2, 'b'), Node(3, 'c', [Node(4, 'd')])]),
    Node(5, 'e', [Node(6, 'f'), Node(7, 'g'), Node(8, 'h')]),
    Node(9, 'i')
]


def _get_choices(nodes, depth=0):
    if not nodes:
        return []
    for node in nodes:
        yield (node.ident, f"{depth * '-'}{node.value}")
        yield from _get_choices(node.children, depth+1)


def get_choices():
    return list(_get_choices(data))


print(result := get_choices())
for __, x in result:
    print(x)

Result:

[(1, 'a'), (2, '-b'), (3, '-c'), (4, '--d'), (5, 'e'), (6, '-f'), (7, '-g'), (8, '-h'), (9, 'i')]
a
-b
-c
--d
e
-f
-g
-h
i

Looks very neat and exactly what I wanted. Ill plug it into my codes and see how it goes. Thanks. Learn something new today, never ever seen yield from before :) — , Dec 27 '21 at 09:36
Would you know if this is faster or there is a way to write up a sql schema to filter for the same result. — , Dec 27 '21 at 09:48
Well, there's alway a nice iterative way to rewrite a recursive function, but it's not always faster and definitely tends to be a bit less easy to read. However, recursion does have a pretty heavy overhead. You can write recursive SQL queries as well, with some work - that would likely be fastest, but also most complicated. It's likely that other changes to your code will be more important, speed-wise — Grismar, Dec 27 '21 at 10:43
If this answer (or another) actually answered your question, please accept it with the checkmark next to it, so that the question no longer appears unanswered (you can still post comments or make changes, as desired) — Grismar, Dec 27 '21 at 10:44

Python output a list in hierarchy

1 Answers1