Breadth First Search (BFS)

Breadth First Search is a search algorithm that explores the tree by exploring all nodes at the present depth prior to moving on to the nodes at the next depth level.

Animation from Wikipedia

This BFS explores nodes from left to right (note that the tree in the animation is not a binary tree)

Implementation

BFS uses a queue to store the nodes that remain to explore. The structure of the queue insures that the nodes of the present depth are explored first (indeed it pops the oldest element which are the one on the

Binary Tree

from collections import deque

def get_depth_bfs(root):
    q = deque()
    q.append((root, 0))

    while q:
        node, i = q.popleft()
        if node:
            q.extend([(node.left, i+1), (node.right, i+1)])
            
    return(i)

Tree

from collections import deque

def get_depth_bfs(root):
    q = deque()
    q.append((root, 0))

    while q:
        node, i = q.popleft()
        if node:
            q.extend([(child_node, i+1) for child_node in node.children])
            
    return(i)