DEV Community

Cover image for Today I Learned: Breadth-First Search on a Tree
Anzhari Purnomo
Anzhari Purnomo

Posted on

Today I Learned: Breadth-First Search on a Tree

#python #beginners #webdev #algorithms

Problem Statement

Implement breadth-first search method on a tree node.

Sample Input 

tree = A / | \ B C D / \ / \ E F G H / \ \ I J K
Enter fullscreen mode Exit fullscreen mode

Sample Result 

["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]
Enter fullscreen mode Exit fullscreen mode

Code #1 

class Node: def __init__(self, name): self.children = [] self.name = name def add_child(self, name): self.children.append(Node(name)) return self def breadth_first_search(self, array): # Write your code here.  queue = [self] while len(queue) > 0: cur_node = queue.pop(0) for child in cur_node.children: queue.append(child) array.append(cur_node.name) return array
Enter fullscreen mode Exit fullscreen mode

Notes

  • Traverse the tree level-by-level.
  • Utilize queue to perform the traversal iteratively.

Credits

Top comments (0)