BFS / level order traversal in Non-Binary Tree using queue

Question

I have to make two classes: NonBinaryTree and SingleNode class containig some methods working on nodes as well as entire tree (in class NonBinaryTree). I have encountered problems with implementing BFS (level order) traversal through Non Binary Tree using queue (first in, first out type). As there are many resources for Binary Tree, where each node have up to two children, I have not found anything that could help me solve problem with Non Binary Tree.

So far, I made this code:


import queue
from typing import List, Callable


class SingleNode:
    def __init__(self, name : str):
        self.name : str = name
        self.children : List['SingleNode'] = []

    def add(self, *nodes : List['SingleNode']):
        for node in nodes:
            self.children.append(node)

    def is_leaf(self):
        if len(self.children) == 0:
            return True
        return False

    def level_order_traversal(self, visit: Callable[['SingleNode'], None]) -> List[List[int]]:
        fifo = queue.Queue()
        levels = []
        fifo.put([root])
        while fifo and root:
            currNode, nextLevel = [], []
            while not fifo.empty():
                node = fifo.get()
                currNode.append(node)
                for child in node.children:
                    nextLevel.append(child)
            fifo.put(nextLevel)
            levels.append(currNode)
        return levels

    def search(self, name : str):
        if self.name == name:
            print(self.__repr__())
        for child in self.children:
            child.search(name)
        return None

    def __str__(self):
        return f"{self.name}"

    def __repr__(self):
        return f"TreeNode({self.name}) : {self.children}"
        
        
class NonBinaryTree:
    root_node: SingleNode

My tree:

enter image description here

I need to go on nodes in this order: 1, 2, 3, 4, 5, 6, 7, 8, and so on...

Anita Anita · Accepted Answer · 2020-12-12T17:30:48

Why don't you follow similar approach as BFS traversal in binary tree, it's just in this case it's non binary but the logic is always gonna be same,

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        levels = []
        queue = [root]
        while queue and root:
            currNode,nextLevel = [],[]
            for node in queue:
                currNode.append(node.val)
                for child in node.children:
                    nextLevel.append(child)
            queue = nextLevel
            levels.append(currNode)
        return levels

BFS / level order traversal in Non-Binary Tree using queue

1 Answers