Breadth-First Search Tree in Python

Breadth-first search (BFS) is a method of visiting all the nodes of a tree or a graph in a breadth-first manner, i.e., visiting all the nodes at a given level before moving to the next level.

Here is a basic implementation of breadth-first search on a tree in Python 3.10:

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = Noneclass BinaryTree:
    def __init__(self):
        self.root = Nonedef breadth_first_search(self):
        if self.root is None:
            return []

        result = []
        queue = deque([self.root])

        while queue:
            node = queue.popleft()
            result.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return result

The above implementation of breadth-first search on a binary tree uses a deque (double-ended queue) data structure to traverse the tree in a breadth-first manner. The breadth_first_search method visits all the nodes at a given level before moving to the next level and returns a list of the nodes' values in the order they were visited.

Time complexity of breadth-first search in a binary tree:

• The time complexity of breadth-first search is O(n), where n is the number of nodes in the tree. This is because each node in the tree is visited exactly once.

Space complexity of breadth-first search in a binary tree:

• The space complexity of breadth-first search is O(n), where n is the number of nodes in the tree. This is because in the worst case, all the nodes of the tree may be stored in the queue.