Tree Traversal Level Order BFS in DSA Javascript

Mental Model

We visit tree nodes level by level, from top to bottom and left to right.

Analogy: Imagine a group of friends standing in rows. You greet everyone in the first row before moving to the next row.

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Binary tree: 1 with children 2 and 3; 2 has children 4 and 5; 3 has child 6

Goal: Visit nodes level by level and print their values in order

Step 1: Start with root node 1 in the queue

Queue: [1]
Visited: []

Why: We begin traversal from the root node

Step 2: Remove 1 from queue, visit it, add its children 2 and 3 to queue

Queue: [2, 3]
Visited: [1]

Why: Visit current node and enqueue its children for next levels

Step 3: Remove 2 from queue, visit it, add its children 4 and 5 to queue

Queue: [3, 4, 5]
Visited: [1, 2]

Why: Continue level order by visiting nodes left to right

Step 4: Remove 3 from queue, visit it, add its child 6 to queue

Queue: [4, 5, 6]
Visited: [1, 2, 3]

Why: Visit next node and enqueue its child

Step 5: Remove 4 from queue, visit it, no children to add

Queue: [5, 6]
Visited: [1, 2, 3, 4]

Why: Leaf node visited, no children to enqueue

Step 6: Remove 5 from queue, visit it, no children to add

Queue: [6]
Visited: [1, 2, 3, 4, 5]

Why: Leaf node visited, no children to enqueue

Step 7: Remove 6 from queue, visit it, no children to add

Queue: []
Visited: [1, 2, 3, 4, 5, 6]

Why: Last node visited, queue empty, traversal done

Result:

Visited nodes in order: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Annotated Code

DSA Javascript

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

function levelOrderBFS(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];

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

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

const traversal = levelOrderBFS(root);
console.log(traversal.join(' -> ') + ' -> null');

if (!root) return [];

handle empty tree by returning empty list

const queue = [root];

initialize queue with root node to start BFS

while (queue.length > 0) {

loop until all nodes are visited

const node = queue.shift();

remove front node from queue to visit it

result.push(node.val);

record visited node's value

if (node.left) queue.push(node.left);

enqueue left child if exists

if (node.right) queue.push(node.right);

enqueue right child if exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) because in worst case the queue holds all nodes at the last level

vs Alternative: Compared to depth-first traversal which uses recursion stack, BFS uses a queue and visits nodes level by level, which is better for shortest path or level-based problems

Edge Cases

Empty tree (root is null)

Returns empty list immediately

DSA Javascript

if (!root) return [];

Tree with only root node

Returns list with single root value

DSA Javascript

while (queue.length > 0) { ... }

Tree with missing children

Only existing children are enqueued, no errors

DSA Javascript

if (node.left) queue.push(node.left);

When to Use This Pattern

When you need to visit nodes level by level or find shortest path in a tree, use level order BFS because it explores nodes in layers from top to bottom.

Common Mistakes

Mistake: Using recursion instead of a queue for level order traversal
Fix: Use a queue to process nodes in FIFO order for correct level order

Mistake: Not checking if left or right child exists before enqueueing
Fix: Add conditionals to enqueue children only if they are not null

Mistake: Using stack instead of queue, which results in DFS instead of BFS
Fix: Use a queue data structure to maintain correct visiting order

Summary

Visits all nodes in a tree level by level from top to bottom and left to right.

Use it when you want to process nodes in order of their depth or find shortest paths in trees.

The key is to use a queue to keep track of nodes to visit next in the correct order.

Practice

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

easy

A. Visits nodes in left subtree, then root, then right subtree

B. Visits nodes in right subtree, then root, then left subtree

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

D. Visits nodes randomly without any order

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes starting from the root, then all nodes at the next level, and so on, moving left to right within each level.

2. Step 2: Compare options with definition

   Visits nodes level by level from top to bottom, left to right matches this definition exactly, while others describe different traversals or incorrect behavior.

3. Final Answer:

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

4. Quick Check:

   Level Order = Top to bottom, left to right [OK]

Hint: Level order means visit nodes level-wise, left to right [OK]

Common Mistakes:

• Confusing level order with inorder or preorder traversal
• Thinking BFS visits nodes randomly
• Mixing left and right subtree orders

2. Which of the following is the correct way to initialize a queue for BFS in JavaScript?

easy

A. const queue = null

B. const queue = {}

C. const queue = 0

D. const queue = []

Solution

1. Step 1: Identify data structure for BFS queue

   BFS uses a queue to hold nodes to visit. In JavaScript, an array can be used as a queue with push and shift methods.

2. Step 2: Check options for correct queue initialization

   const queue = [] initializes an empty array, suitable for queue operations. Others are incorrect types for queue usage.

3. Final Answer:

   const queue = [] -> Option D

4. Quick Check:

   Queue = array for BFS [OK]

Hint: Use an empty array [] as queue for BFS in JavaScript [OK]

Common Mistakes:

• Using object {} instead of array for queue
• Initializing queue as null or number
• Not knowing how to enqueue/dequeue in JS

3. What is the output of the following code snippet?

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

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

function levelOrder(root) {
  const result = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

console.log(levelOrder(root));

medium

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

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

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

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

Solution

1. Step 1: Trace the BFS traversal on the tree

   Start with root (1), then enqueue left (2) and right (3). Next dequeue 2, enqueue its children 4 and 5. Then dequeue 3 (no children). Then dequeue 4 and 5.

2. Step 2: Collect visited nodes in order

   Visited order is 1, 2, 3, 4, 5 as nodes are processed level by level, left to right.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option A

4. Quick Check:

   Level order output = [1, 2, 3, 4, 5] [OK]

Hint: Follow queue order: root, left child, right child [OK]

Common Mistakes:

• Mixing preorder or inorder output with BFS
• Forgetting to enqueue children in correct order
• Confusing shift() with pop() in queue

4. Find the error in this BFS code snippet for a binary tree:

function bfs(root) {
  const queue = [];
  queue.push(root);
  while (queue.length > 0) {
    const node = queue.pop();
    console.log(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

medium

A. Not checking if root is null before pushing

B. Using pop() instead of shift() causes wrong traversal order

C. Missing return statement

D. Using console.log instead of return

Solution

1. Step 1: Identify queue operation used

   The code uses pop() to remove nodes from the queue, which removes from the end (stack behavior).

2. Step 2: Understand BFS queue behavior

   BFS requires removing nodes from the front (shift()), not the end. Using pop() reverses order, causing DFS-like traversal.

3. Final Answer:

   Using pop() instead of shift() causes wrong traversal order -> Option B

4. Quick Check:

   BFS needs shift(), not pop() [OK]

Hint: Use shift() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Confusing pop() with shift() in queue
• Ignoring null root check (less critical here)
• Expecting return instead of console.log (not error)

5. Given a binary tree, how can you modify level order traversal to return nodes level by level as nested arrays?
Example tree:

    1
   / \
  2   3
 / \
4   5

hard

A. Use a queue and track the number of nodes at each level to group values

B. Use recursion to visit nodes in preorder and group by depth

C. Use a stack to reverse the order of nodes after traversal

D. Traverse left subtree fully before right subtree and collect nodes

Solution

1. Step 1: Understand grouping nodes by level

   To return nodes level by level, we must know how many nodes are at each level during traversal.

2. Step 2: Use queue size to separate levels

   At each iteration, record queue length (nodes at current level), dequeue exactly that many nodes, collect their values, then enqueue their children for next level.

3. Step 3: Compare options

   Use a queue and track the number of nodes at each level to group values describes this approach correctly. Others describe preorder recursion, stack reversal, or incorrect traversal orders.

4. Final Answer:

   Use a queue and track the number of nodes at each level to group values -> Option A

5. Quick Check:

   Queue + level size tracking = nested level arrays [OK]

Hint: Track queue length each loop to separate levels [OK]

Common Mistakes:

• Trying to use recursion without level info
• Using stack which reverses order incorrectly
• Not grouping nodes, returning flat list instead