Coding Interview Questions | Level Order Traversal

January 11th, 2024

Level Order Traversal Problem Introduction:

This summary will talk about my solution to the level order traversal problem as seen on leetcode here.

How do you solve the Level Order Traversal Problem using Breadth-First-Search?

Solution:

function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) {
    return [];
  }

  // Assume we have data structure that can grab
  // value at front of queue in O(1) time
  const nodeQueue: { node: TreeNode; depth: number }[] = [
    { depth: 0, node: root },
  ];
  const nodeValues: number[][] = [];

  while (nodeQueue.length > 0) {
    const { depth, node } = nodeQueue.shift()!;

    // If we haven't traversed this level yet,
    // add initial array to values at this level
    if (nodeValues.length <= depth) {
      nodeValues.push([node.val]);
    } else {
      nodeValues[depth].push(node.val);
    }

    if (node.left) {
      nodeQueue.push({ depth: depth + 1, node: node.left });
    }

    if (node.right) {
      nodeQueue.push({ depth: depth + 1, node: node.right });
    }
  }

  return nodeValues;
}

Level Order Traversal Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Base Case Handling: The solution begins by checking if the root node is null. If so, it returns an empty array, indicating that there are no nodes to traverse.
2. Breadth-First Traversal: The algorithm utilizes a breadth-first traversal approach using a queue (nodeQueue). The queue initially contains the root node with a depth of 0.
3. Level Order Construction: The algorithm iterates through the nodes in the queue, tracking their depth. It constructs the level order traversal by creating arrays for each level (nodeValues). If a level array doesn’t exist, it is initialized; otherwise, the node value is added to the existing array.
4. Queue Operations: Nodes are dequeued from the front of the queue, and their children are enqueued in the order they appear. This ensures a left-to-right traversal of the tree level by level.

Complexities:

1. Time Complexity: The time complexity is determined by the number of nodes in the binary tree, making it O(n), where n is the number of nodes.
2. Space Complexity: The space complexity is O(n), where n is the number of nodes in the binary tree. All node values are stored in the nodeValues array, contributing to the overall space complexity.