Today I Learned: Breadth-First Search on a Tree

anzhari

Anzhari Purnomo

Posted on September 6, 2020

Today I Learned: Breadth-First Search on a Tree

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

💖 💪 🙅 🚩
anzhari
Anzhari Purnomo

Posted on September 6, 2020

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related