Tree Traversal Level Order BFS in DSA Typescript - Time & Space Complexity

Time Complexity: Tree Traversal Level Order BFS

O(n)

Understanding Time Complexity

We want to understand how long it takes to visit all nodes in a tree using level order traversal.

The question is: how does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];
    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;
}

This code visits each node in the tree level by level, collecting values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs as long as there are nodes in the queue, and the inner for loop processes each node at the current level.
• How many times: Each node is visited exactly once, so the total number of iterations equals the number of nodes n.

How Execution Grows With Input

As the tree grows, the number of nodes increases, and each node is visited once.

Input Size (n)	Approx. Operations
10	About 10 visits and queue operations
100	About 100 visits and queue operations
1000	About 1000 visits and queue operations

Pattern observation: The operations grow linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the traversal grows directly in proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because there are nested loops, the time complexity is quadratic O(n²)."

[OK] Correct: The inner loop runs only for the nodes at each level, and all nodes together are visited once, so total work is linear, not quadratic.

Interview Connect

Understanding level order traversal time helps you explain how breadth-first search works efficiently on trees, a common topic in interviews.

Self-Check

"What if we used a depth-first traversal instead? How would the time complexity change?"