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 · Accepted Answer · 2020-12-12 17:30:48Z

1

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

answered Dec 12, 2020 at 17:30

Anita

938 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

PrertoQuebas Over a year ago

Thanks! However I don't understand everything here. I adapted your code to my clas variables and requirements, but it still doesn't work.

Anita Over a year ago

Could you please share what error you're receiving, may be I can try to help. Also, I could not write the complete code for you as on so we can just share the steps or give hint but can't provide a complete working solution.

Shima Mahmoud · Accepted Answer · 2023-07-23 14:39:57Z

I have created a solution in Java to let’s say print the tree nodes in the level order.

I hope it can help.

The solution uses Queue DS.

The solution algorithm:

1- define an instance of a queue DS

2- add the root to the queue

3- iterate using the while (queue is not empty) condition

4- define String treeStr

5- define childParentMap of type Map DS to keep each child's parent

---iteration steps

 1- remove from the queue and add in the root item

 2- `treeStr.append(root.val)` or perform any other operation

 3- if (root has children) add all of them to the end of the queue

 4- If the parent is needed in another step or operation

 5- (optional) Add `(root->child)` `childParentMap` to be able to retrieve parent elsewhere.

This is the java solution:

public void bfsTraverseByQueue(Node root) {
        Queue<Node> q = new LinkedList<>();

        // enque childs Elements to the queue

        q.add(root);

        while (!q.isEmpty()) {

            root = q.remove();

            System.out.println(root.getVal() + " ");

            q.addAll(root.getChildren());
        }
    }

I also used a translator to translate the above code into python:

from collections import deque

class TraverseNonBinaryTree:
    def traverseByQueue(self, root):
        q = deque()
        
        q.append(root)
        while q:
            root = q.popleft()
            print(root.getVal(), end=" ")
            q.extend(root.getChildren())

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related