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);
    }
  }
}