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?"

Practice

1. What does the Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in preorder (root, left, right)

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in inorder (left, root, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand Level Order Traversal

   Level Order Traversal visits nodes level by level starting from the root, moving left to right on each level.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder are depth-first traversals, not level by level.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level Order = BFS = top to bottom, left to right [OK]

Hint: Level order means visit nodes by levels, not depth [OK]

Common Mistakes:

• Confusing level order with preorder traversal
• Thinking BFS visits nodes depth-first
• Mixing up traversal orders

2. Which of the following TypeScript code snippets correctly initializes a queue for BFS traversal?

easy

A. const queue: TreeNode[] = []; queue.push(root);

B. const queue = new Set(); queue.add(root);

C. const queue = new Map(); queue.set(0, root);

D. const queue = {}; queue.enqueue(root);

Solution

1. Step 1: Identify correct queue initialization

   In TypeScript, an array can be used as a queue with push and shift methods.

2. Step 2: Check each option

   const queue: TreeNode[] = []; queue.push(root); uses an array and push, which is correct. const queue = new Set(); queue.add(root); uses Set which is unordered. const queue = new Map(); queue.set(0, root); uses Map which is key-value, not queue. const queue = {}; queue.enqueue(root); uses an object with enqueue method which does not exist.

3. Final Answer:

   const queue: TreeNode[] = []; queue.push(root); -> Option A

4. Quick Check:

   Array with push/shift = queue [OK]

Hint: Use array with push and shift for queue in TypeScript [OK]

Common Mistakes:

• Using Set or Map instead of array for queue
• Calling non-existent enqueue method on object
• Not initializing queue before use

3. Given the binary tree below, what is the output of the level order traversal?

    1
   / \
  2   3
 /   / \
4   5   6

function levelOrder(root: TreeNode | null): number[] { if (!root) return []; const queue: TreeNode[] = [root]; const result: number[] = []; while (queue.length > 0) { const node = queue.shift()!; result.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; }

medium

A. [1, 2, 4, 3, 5, 6]

B. [1, 3, 2, 6, 5, 4]

C. [1, 2, 3, 4, 5, 6]

D. [4, 2, 5, 3, 6, 1]

Solution

1. Step 1: Trace the queue and result arrays

   Start with queue = [1], result = []. Remove 1, add to result: [1]. Add children 2 and 3 to queue: [2,3]. Remove 2, add to result: [1,2]. Add child 4: queue = [3,4]. Remove 3, add to result: [1,2,3]. Add children 5 and 6: queue = [4,5,6]. Remove 4, add to result: [1,2,3,4]. No children. Remove 5, add to result: [1,2,3,4,5]. No children. Remove 6, add to result: [1,2,3,4,5,6]. No children.

2. Step 2: Confirm final output

   The final result array is [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option C

4. Quick Check:

   Level order visits nodes level-wise: [1,2,3,4,5,6] [OK]

Hint: Follow queue order: push children left then right [OK]

Common Mistakes:

• Mixing left and right child order
• Confusing preorder with level order output
• Forgetting to add children to queue

4. The following TypeScript code for level order traversal has a bug. What is the error?

function levelOrder(root: TreeNode | null): number[] {
  const queue: TreeNode[] = [];
  const result: number[] = [];
  queue.push(root!);
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

medium

A. It pushes children after adding node to result

B. It uses shift() instead of pop() on the queue

C. It returns result before the loop ends

D. It does not check if root is null before pushing

Solution

1. Step 1: Analyze root null check

   The code pushes root! without checking if root is null. If root is null, queue contains null and node.val will cause runtime error.

2. Step 2: Verify other parts

   Using shift() is correct for queue. Adding children after node is correct. Return is after loop ends.

3. Final Answer:

   It does not check if root is null before pushing -> Option D

4. Quick Check:

   Always check root null before queue push [OK]

Hint: Check root null before queue push to avoid errors [OK]

Common Mistakes:

• Ignoring null root check
• Confusing shift() with pop() for queue
• Misplacing return statement

5. You want to print the level order traversal of a binary tree but separate each level on a new line. Which approach correctly achieves this in TypeScript?

function levelOrderByLevel(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;
}

hard

A. Use a loop for each level size, collect nodes, then push to result

B. Push all nodes to result as a flat array without levels

C. Use recursion to print nodes without queue

D. Add all children to queue before processing current level

Solution

1. Step 1: Understand level separation logic

   Using levelSize to track nodes at current level allows processing nodes level by level.

2. Step 2: Check code correctness

   Loop runs levelSize times, collects node values in currentLevel, adds children to queue for next level, then pushes currentLevel to result.

3. Final Answer:

   Use a loop for each level size, collect nodes, then push to result -> Option A

4. Quick Check:

   Track level size, process nodes per level [OK]

Hint: Use queue length to separate levels in BFS [OK]

Common Mistakes:

• Not separating levels, returning flat array
• Using recursion instead of queue for BFS
• Adding children before processing current level nodes