Tree BFS (Level-By-Level)

We need to use a queue (FIFO).

For each time you're at the queue, you need to empty out the queue and add in the relevant nodes.

def bfsTree(treeRoot: TreeNode) -> None:
    if not treeRoot:
        return None

    currentLevelNodes = deque([treeRoot])

    while currentLevelNodes:
        for i in range(len(currentLevelNodes)):
	        # This loop here to dishtinguish the level 
	        # Whatever happens here will only be in the same level
            currNode = currentLevelNodes.popleft()
            visit(currNode)

            if currNode.left:
                currentLevelNodes.append(currNode.left)
            if currNode.right:
                currentLevelNodes.append(currNode.right)

Java

public static <T> void bfsTraversal(TreeNode<T> root) {
  TreeNode<T> currNode = root;
  Deque<TreeNode<T>> queue = new ArrayDeque<>(List.of(currNode));

  while (!queue.isEmpty()) {
    for (var i = 0; i < queue.size(); i++) {
      currNode = queue.poll();

      System.out.println("visit " + currNode.val);
      if (currNode.left != null) {
        queue.add(currNode.left);
      }


      if (currNode.right != null) {
        queue.add(currNode.right);
      }
    }
  }
}

with class TreeNode

class TreeNode:
    __slots__ = ["left", "right", "value"]

    def __init__(self, value: int) -> None:
        self.left = None
        self.right = None
        self.value = value

Time Complexity:

• $O(n)$
  • $n$: Number of node in the tree