Tree Traversal Level Order BFS in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this level order traversal?

Given the binary tree below, what is the printed output of the level order traversal (BFS)?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(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;
}

console.log(levelOrder(root));

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

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

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

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

💡 Hint

Think about visiting nodes level by level from left to right.

Level order traversal visits nodes level by level from left to right. Starting at root 1, then nodes 2 and 3, then nodes 4, 5, and 6.

❓ Predict Output

intermediate

What is the output of this level order traversal with null children?

Consider this binary tree with some missing children. What is the output of the level order traversal?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(10,
  new TreeNode(20, null, new TreeNode(40)),
  new TreeNode(30)
);

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

console.log(levelOrder(root));

A [10, 40, 20, 30]

B [10, 30, 20, 40]

C [10, 20, 40, 30]

D [10, 20, 30, 40]

💡 Hint

Remember to add children to the queue only if they exist.

The traversal visits root 10, then its children 20 and 30, then the child 40 of node 20.

🔧 Debug

advanced

Why does this level order traversal code cause an error?

This code is intended to perform a level order traversal but throws an error. What is the cause?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

A Using pop() removes nodes from the end, causing a depth-first traversal, not level order.

B The queue is empty initially, so the loop never runs.

C The code tries to access node.val before checking if node is null.

D The code pushes children in wrong order causing incorrect output.

💡 Hint

Think about how queue operations affect traversal order.

Using pop() removes the last element, making the structure behave like a stack, resulting in depth-first traversal instead of breadth-first.

🚀 Application

advanced

How many nodes are visited in this level order traversal?

Given the tree below, how many nodes will be visited during the level order traversal?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(7,
  new TreeNode(3,
    new TreeNode(1),
    null
  ),
  new TreeNode(9,
    new TreeNode(8),
    new TreeNode(10)
  )
);

A 7

B 5

C 6

D 4

💡 Hint

Count all nodes including root and children.

The tree has nodes: 7, 3, 9, 1, 8, 10 totaling 6 nodes.

🧠 Conceptual

expert

Which data structure is essential for implementing level order traversal (BFS) on a tree?

To perform a level order traversal on a binary tree, which data structure is used to keep track of nodes to visit next?

A Priority Queue

B Queue

C Hash Map

D Stack

💡 Hint

Think about the order nodes are visited in BFS.

A queue is used to process nodes in the order they are discovered, ensuring level by level traversal.