Ask LSBot
Back to Open Book Shelf

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]

Exercises

  1. Decide which data structure is appropriate, then write an algorithm to solve the problem.

    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.

    View Our Solution

    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:

    1. We'll begin by adding the root node to the queue and initializing the result array.

    2. 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.

    3. We'll repeat the steps above until no elements are left in the queue.

    4. 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.

  2. Implement a solution that performs a level-order traversal of a binary tree.

    View Our Solution

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

  3. Identify the time and space complexity of your level-order traversal.

    View Our Solution

    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.

Previous:  Practice: Postorder Traversal
Next:  Binary Search Tree

Ask LSBot about: Practice: Level Order Traversal

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Practice: Level Order Traversal - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.