Skip to content

Latest commit

 

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README.md

Breath First Search

When to use

Any problem involving the traversal of a tree in a level-by-level order can be efficiently solved by using this approach. We will use a Queue to keep track of all the nodes of a level before we jump onto the next level. This also means that the space complexity of the algorithm will be O(W), where W is the maximum number of nodes on any level.

Pseudo code

const levelNodes = [root];
while (levelNodes.length > 0) {
  const levelLength = levelNodes.length;
  for (let i = 0; i < levelLength; i++) {
    const node = levelNodes.shift();
    aggregateLevelNode(node);
    if (node.left) {
      levelNodes.push(node.left);
    }
    if (node.right) {
      levelNodes.push(node.right);
    }
  }
}