Practice: Level Order Traversal

In this assignment, your task is to solve the "Level Order Traversal" problem. Try solving the problem on your own. This solution is quite different from the DFS problems, so expect to take a bit more time thinking it through and remember to utilize PEDAC.

Problem Description

// Given the root node of a binary tree, implement a
// function `bfs` that returns an array containing the
// values of the nodes visited in level order
// (or breadth-first-search) traversal.

class Node {
  constructor(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }
}

// Helper function for test cases
function buildTree(arr) {
  if (arr.length === 0) {
    return null;
  }

  const nodes = [];

  const val = arr.shift();
  const root = new Node(val);
  nodes.push(root);

  while (arr.length > 0) {
    const curr = nodes.shift();

    const leftVal = arr.shift();
    if (leftVal !== null) {
      curr.left = new Node(leftVal);
      nodes.push(curr.left);
    }

    if (arr.length > 0) {
      const rightVal = arr.shift();
      if (rightVal !== null) {
        curr.right = new Node(rightVal);
        nodes.push(curr.right);
      }
    }
  }

  return root;
}

// Test cases
const tree1 = buildTree([1, null, 2, 3]);
console.log(bfs(tree1)); // Output: [1, 2, 3]

const tree2 = buildTree([1, 2, 3, null, null, 4, null, null, 5]);
console.log(bfs(tree2)); // Output: [1, 2, 3, 4, 5]

const tree3 = buildTree([5, 3, null, 2, null, 1, null]);
console.log(bfs(tree3)); // Output: [5, 3, 2, 1]

const tree4 = buildTree([10, 5, 15, null, 6, 12, 21, null, null, 11]);
console.log(bfs(tree4)); // Output: [10, 5, 15, 6, 12, 21, 11]

Walkthrough & Solution

A queue data structure would be helpful to keep track of the nodes we need to process and the order in which to do so.

We've been solving depth-first search problems using recursion, and we know we can also solve them using a stack. However, this is not the case for breadth-first search.

Here, since we need nodes in level-by-level order, we have to use a queue. We'll use an array as a queue in our solution.

Let's look at the algorithm:

We'll begin by adding the root node to the queue and initializing the result array.
Next, in each iteration, we are going to:
- Dequeue a node from the queue and process it (add its value to the result array)
- If the node has a left child, we are going to enqueue it.
- If the node has a right child, we are going to enqueue it.
We'll repeat the steps above until no elements are left in the queue.
In the end, we'll return the result array.

Let's do a walkthrough using the example tree from the previous assignments:

Step 1: We begin with the root node in the queue.

Step 2: In the first iteration, we dequeue node 1, add its value to the result array, and then enqueue its children, first the left child 2 and then the right child 3.

Step 3: In the next iteration we dequeue node 2 and add its value to the result array. This node doesn't have any children, so we will continue.

Step 4: In the next iteration, we repeat the process. First, we dequeue the node from the queue, node 3, and add its value to the result array. Then, we enqueue its left child, node 4 to the result array. This node doesn't have a right child, so we continue.

Step 5: In this iteration, we dequeue node 4 from the queue and add its value to the result array. Then we enqueue its right child, node 5 to the queue as it doesn't have a left child.

Step 6: In the final iteration, we dequeue node 5 from the queue. Since this node has no children and the queue is empty, we are done with the iterations and can return the result.

Time and Space Complexities

Time Complexity: O(N), where N is the number of nodes in the tree. This is because we need to visit each node exactly once.

Space Complexity: While the space complexity in binary tree problems is usually O(h), where h is the height of the tree, when we are doing a breadth-first search, we are populating the queue level by level. Therefore, the maximum queue size is not the height but the maximum width of the tree. Thus, the space complexity is O(w), where w is the maximum width of the binary tree.

function bfs(root) {
  const result = [];
  if (root === null) {
      return result;
  }

  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);

    if (node.left !== null) {
      queue.push(node.left);
    }
    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}