How do you print all nodes in a specific level?

Question

I want to figure out how to print all nodes at a specific level. Right now, I can get to that level but I can only print out a part of the nodes. How would I get it to print all the nodes from all branches instead of nodes from one branch? I tried recursively calling get_level_nodes but it keeps outputting an error.

import random


class Node(object):

    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

    def create_children(self, infects, depth):
        # root node
        if depth == 0:
            return

        for i in range(infects):
            rand2 = random.random()

            if rand2 <= 0.37:
                if rand2 <= 0.02:
                    child = Node('NA')
                else:
                    child = Node('CA')
            else:
                if rand2 <= 0.5:
                    child = Node('NS')
                else:
                    child = Node('CS')

            child.parent = self
            child.grandparent = self.parent
            self.children.append(child)

            # recursive call to create more child nodes
            child.create_children(infects, depth-1)

    def tree_level(self):
        level = 0
        p = self.parent

        while p:
            level += 1
            p = p.parent

        return level

    def print_tree(self):
        spaces = ' ' * self.tree_level() * 2
        prefix = spaces + '|__' if self.parent else ''
        print(prefix + self.value, self.quarantined)

        if self.children:
            for child in self.children:
                if child.value != None:
                    child.print_tree()

    def get_level_nodes(self, cur_level):
        level = 0
        c = self.children
        while c:
            level += 1
            c = self.children
            if level == cur_level:
                return c

if __name__ == "__main__":
    rand1 = random.random()

    if rand1 <= .35:
        a = Node('CA')
    else:
        a = Node('CA')

    a.create_children(2, 5)     # create_children(R0, depth)

    for child in a.get_level_nodes(4):
        print(child.value)
    a.print_tree()

Related: [Binary tree number of nodes with a given level](https://stackoverflow.com/questions/2853189/binary-tree-number-of-nodes-with-a-given-level) - C++ tag but has algorithmic answers. Also: [Printing BFS (Binary Tree) in Level Order with Specific Formatting](https://stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting) — wwii, Dec 03 '20 at 19:33
..When the tree is built or modified keep a dictionary with the level as keys and nodes in that level as the values. Then you won't have to *calculate* it later. — wwii, Dec 03 '20 at 19:39
Please supply the expected [minimal, reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). Show where the intermediate results differ from what you expected. We should be able to copy and paste a contiguous block of your code, execute that file, and reproduce your problem along with tracing output for the problem points. This lets us test our suggestions against your test data and desired output. This code is not minimal; you haven't traced or shown the problems. — Prune, Dec 03 '20 at 20:07

trincot · Accepted Answer · 2020-12-04T08:22:44.167

Your get_level_nodes function has some issues:

c never changes value: it always represents self.children, so you are not actually moving down in the tree. You should somewhere iterate over those children and extend your collection of nodes with the children of these children.
You start out with self.children, but that list of nodes already represents the second level in the tree. You should foresee that the function can return the top-level of the tree, i.e. a list with just the root node in it.

I'll assume that you use the definition of "level" as specified in Wikipedia, although other definitions exist:

Level
1 + the number of edges between a node and the root, i.e. (depth + 1)

Solution:

    def get_level_nodes(self, cur_level):
        nodes = [self]
        for i in range(cur_level-1):  # assuming that cur_level is at least 1
            children = []
            for node in nodes:
                children.extend(node.children)
            nodes = children
        return nodes

How do you print all nodes in a specific level?

1 Answers1