Breadth-first search

BSF has its common pattern.

Pattern for problems with many steps and each step has many ways to next step:

a queue stores [step0, step1, step2, ...]

queue.add(first step)

while queue is not empty

  current_step = queue.poll()
  
  // do something here with current_step
  // like counting
  
  foreah step in current_step can jump to
    queue.add(step)
    

Apply the pattern

It is easy to search through a binary tree using BSF.

queue.add(root)

while queue is not empty

  current_node = queue.poll()
 
  add current_node.value to current level collections
 
  queue.add(current_node.left)
  queue.add(current_node.right)

How to know which level current node should be added to

use a dummy node as a separator into the queue, whenever polling a separator from the queue, we know that a level is end.

codes may be like below

queue.add(root)
queue.add(SEP)


while queue is not empty

  current_node = queue.poll()
 
  if current_node is SEP
    
    // new level is start
    reset current_level collection
    
    queue.add(SEP) // here is added to the end of current level
    
    stop if only SEP in the queue
    
  else
    
    add current_node.value to current_level collection
  
    queue.add(current_node.left)
    queue.add(current_node.right)