Getting Started with Trees: Breadth First Search(BFS)

In this article, we’ll be exploring the world of Breadth-First Search (BFS), which is a popular algorithm used for searching, finding the shortest path between two nodes, and discovering the connectivity of a tree(graph).

In our previous article, we discussed Depth-First Search (DFS), which is a graph traversal algorithm that explores the tree(graph) in a depth-first manner. But now, we’re going to dive into the world of BFS, which explores the tree(graph) level by level.

If you are ready, let’s get started!

What is Breadth First Search?

Breadth First Search (BFS) is a traversal algorithm that explores all the vertices of a graph or a tree level by level. It starts at the root node or an arbitrary node and visits all the nodes at the same level before moving on to the next level.

The algorithm works by maintaining a queue of nodes that need to be visited. It starts by adding the initial node to the queue and marking it as visited. Then, it dequeues the node from the front of the queue and visits all its neighboring nodes that haven’t been visited yet.

Each unvisited neighboring node is added to the back of the queue. The algorithm continues dequeuing nodes and visiting their neighbors until the queue is empty. Let’s see an example of this process.

Consider the following binary tree.

           1
         /   \
        2     3
       / \   / \
      4   5 6   7

Assume we want to traverse the tree using BFS. The first step is to add node 1 to the queue and mark it as visited. Then, we dequeue node 1 from the front of the queue and visit its neighbors, which are nodes 2 and 3. We add nodes 2 and 3 to the back of the queue, as they are the next level of nodes to be visited.

Queue: [2, 3]
Visited: [1]

Next, we dequeue node 2 from the front of the queue and visit its neighbors, which are nodes 4 and 5. We add nodes 4 and 5 to the back of the queue, as they are the next level of nodes to be visited.

Queue: [3, 4, 5]
Visited: [1, 2]

We then dequeue node 3 from the front of the queue and visit its neighbors, which are nodes 6 and 7. We add nodes 6 and 7 to the back of the queue, as they are the next level of nodes to be visited.

Queue: [4, 5, 6, 7]
Visited: [1, 2, 3]

We continue dequeuing nodes and visiting their neighbors until the queue is empty. The final order of visited nodes using BFS is:

Visited: [1, 2, 3, 4, 5, 6, 7]

BFS Related Problems

102. Binary Tree Level Order Traversal

The question: Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

The approach: We will follow this process:

1. Create two arrays: one to store the level-order traversal of the tree( let’s say ‘result’) and another one to hold the nodes to be processed (let’s say ‘queue’).
2. Push the root node into the queue.
3. While the queue is not empty:

• Determine the number of nodes in the current level by storing the current length of the queue in a variable.
• Create an empty currentLevel array to store the nodes at the current level.
• Iterate over the nodes in the current level by dequeuing levelSize number of nodes from the queue.
• Push the values of each dequeued node into the currentLevel array.
• If a dequeued node has a left child, enqueue the left child into the queue.
• If a dequeued node has a right child, enqueue the right child into the queue.
• Once all nodes in the current level have been processed, push the currentLevel array into the result array.

4. Return the result array containing the values of each node in level-order.

var levelOrder = function(root) {
    if (!root) {
        return [];
    }
    
    const result = [];
    const queue = [];
    
    queue.push(root);
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        
        result.push(currentLevel);
    }
    
    return result;
};

The time complexity of the given code is O(n), where n is the number of nodes in the tree. This is because the code performs a breadth-first traversal of the tree, which visits each node once.

The space complexity of the given code is O(w), where w is the maximum width of the tree, which is the number of nodes in the level with the most nodes. This is because the code uses a queue to store the nodes at each level of the tree. The maximum number of nodes that can be in the queue at any given time is the width of the tree. However, considering we are looking for the worst cases all the time and we can approximate the notations we can say m ~ n/2 for binary trees and the space complexity will be still O(n).

429. N-ary Tree Level Order Traversal

The question: Given an n-ary tree, return the level order traversal of its nodes’ values.

The approach: We shouldn’t miss the chance to practice our skills beyond binary trees, right?

The main difference between binary tree and n-ary tree traversal is that binary tree traversal processes only two children per node, while n-ary tree traversal processes any number of children per node.

We will go through with the same approach as the previous question. However, instead of looking right and left children of the node, we will go through all of its children in a loop.

var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            for (let child of node.children) {
                queue.push(child);
            }
        }
        
        result.push(currentLevel);
    }
    
    return result;
};

The time complexity of this code is O(n), where n is the total number of nodes in the n-ary tree. This is because we visit each node in the tree exactly once during the traversal, and the time taken to visit each node and enqueue its children is constant.

The space required by the queue is proportional to the number of nodes in the tree, so its space complexity is also O(n).

637. Average of Levels in Binary Tree

The problem: Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

The approach: The approach of this question is quite similar with level order traversal of a binary tree.

• We keep track of the size of the current level by storing the length of the queue at the beginning of each iteration.
• We also keep track of the sum of the node values in the current level.
• We use a for loop to process each node in the current level. We dequeue a node from the front of the queue and add its value to the variable that we hold the sum of the current level.
• If the dequeued node has left and/or right children, we enqueue them to the back of the queue.
• Once all nodes in the current level have been processed, we calculate the average value of the nodes by dividing the sum of the level by the level size.

var averageOfLevels = function(root) {
  if (!root) return [];

  let queue = [root];
  let averages = [];

  while (queue.length > 0) {
    const levelSize = queue.length;
    let levelSum = 0;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      levelSum += node.val;

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    const levelAvg = levelSum / levelSize;
    averages.push(levelAvg);
  }

  return averages;
    
};

The time complexity of this code is O(n) -same reason with the previous questions-.

The space complexity of the function is also O(n), because in the worst case scenario, the queue could hold all the nodes of the last level of the tree, which is roughly half of the total number of nodes in a complete binary tree(still counts as O(n)).

103. Binary Tree Zigzag Level Order Traversal

The problem: Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). As an example:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

The approach: We use a while loop to process each level of the tree.

• We keep track of the size of the current level and create an empty array to store the node values.
• We dequeue each node from the front of the queue, add its value to the array, and enqueue its children (if any).
• After all nodes in the level have been processed, we reverse the order of the node values if isReverse is true, push the array to the result, toggle the value of isReverse, and repeat until the queue is empty.

The time and the space complexity of the function are both O(n) -same reasons with the previous questions-.

function zigzagLevelOrder(root) {
  if (!root) return [];

  const queue = [root];
  const result = [];
  let isReverse = false;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const levelValues = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      levelValues.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    if (isReverse) levelValues.reverse();
    result.push(levelValues);
    isReverse = !isReverse;
  }

  return result;
}

This was the first solution that came to my mind but if you notice, I used a build-in reverse function inside my solution.

The time complexity of this reverse function is O(n) where n is the length of the array being reversed. This is because the function needs to traverse the entire array and swap the elements from the beginning and end until the midpoint of the array is reached. (no space complexity addition because it is an in-place reversing of the elements)

If you would like to avoid using this function, we can come up with an alternative.

We can use the unshift method to insert each node's value at the beginning of the array when we are in a reverse level. This way, we can achieve the same zigzag level order traversal as before without using the reverse method.

var zigzagLevelOrder = function(root) {
  if (!root) return [];

  const queue = [root];
  const result = [];
  let isReverse = false;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const levelValues = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      if(!isReverse) {
        levelValues.push(node.val);
      } else {
        levelValues.unshift(node.val);
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(levelValues);
    isReverse = !isReverse;
  }

  return result;
}

515. Find Largest Value in Each Tree Row

The question: Given the root of a binary tree, return an array of the largest value in each row of the tree.

The approach:

1. We need to keep track of the maximum value in each level. In the corrected code, we initialize max to -Infinity before the for loop and update it to the maximum value in the current level as we iterate over the nodes.
2. We push the maximum value in the current level to the result array after iterating over all the nodes in the current level.
3. We return an empty array if root is null or undefined.

var largestValues = function(root) {
    if (!root) return [];

    const queue = [root];
    const result = [];

    while (queue.length > 0) {
        const size = queue.length;
        let max = -Infinity;

        for (let i = 0; i < size; i++) {
            const node = queue.shift();

            max = Math.max(max, node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(max);
    }

    return result;
};

Time and space complexity are both O(n), where n is the number of nodes in the tree because of the same reasons with previous questions.

Note that in general, the space complexity of a breadth-first search algorithm is proportional to the maximum number of nodes that can be in the queue at any given time, which is the number of nodes in the last level of the tree.

Conclusion

In this blog post, we learned that BFS uses a queue data structure to store nodes in a level-wise manner and visited them in the order they were added to the queue. This ensures that we process all the nodes at the same level before moving on to the next level, making it an efficient algorithm for tree traversal.

BFS is a simple yet powerful algorithm that can be used in various applications such as searching, graph traversal, and path-finding. Its ability to find the shortest path in a graph makes it a valuable tool in many real-world problems. However, it is crucial to be careful when implementing BFS to avoid errors such as infinite loops. With the right precautions, BFS is a valuable addition to any developer’s toolkit.