This algorithm is used to search or traverse a tree or graph. It explores all nodes at the current depth before moving on to nodes a the next level. Use this when you think the data you are looking for is close to the starting node, rather than far away from it. If you think it is far away use a depth first search instead.

An iterative approach using a queue to keep track of the nodes to explore is generally used.

Time Complexity: O(V + E) where V is the number of verticies and E is the number of edges.

Traversal of a tree is similar to a graph except the visited collection is not needed. This is because a tree does not have cycles in it. So, we do not need to keep track of the nodes we have already visited.

classTreeNode(object):def__init__(self,x): self.val = x self.left =None self.right =Nonedefbfs_traversal(root: TreeNode) -> List[int]:ifnot root:return [] queue =deque() queue.append(root) result = []while queue: node = queue.popleft()if node: result.append(node.val) queue.append(node.left) queue.append(node.right)return result