Tree Traversal Level Order BFS in DSA Typescript - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: You are working with a simple family tree where each person can have children. You want to visit each person level by level, starting from the oldest ancestor, then their children, then grandchildren, and so on.

🎯 Goal: Build a program that performs a level order traversal (Breadth-First Search) on a tree structure and prints the values of nodes level by level.

📋 What You'll Learn

Create a tree node class with a value and children array

Create a sample tree with exact nodes and structure

Use a queue to traverse the tree level by level

Print the values of nodes in level order separated by spaces

💡 Why This Matters

🌍 Real World

Level order traversal is used in many real-world scenarios like social networks to find friends at each level, or in file systems to list files by folder depth.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with hierarchical data, search algorithms, and building efficient data processing pipelines.

1

Create TreeNode class and build the tree

Create a class called TreeNode with a constructor that takes a value of type string and initializes a children array as empty. Then create the following tree nodes exactly:
const root = new TreeNode('Grandparent'),
const parent1 = new TreeNode('Parent1'),
const parent2 = new TreeNode('Parent2'),
const child1 = new TreeNode('Child1'),
const child2 = new TreeNode('Child2'). Finally, build the tree by adding parent1 and parent2 as children of root, and child1 and child2 as children of parent1.

DSA Typescript

// Your code here to create TreeNode class and build the tree

Hint

Define the class first, then create nodes with the exact names and values. Use push to add children.

2

Create a queue to help with level order traversal

Create a variable called queue and initialize it as an array containing only the root node.

DSA Typescript

class TreeNode {
    value: string;
    children: TreeNode[];
    constructor(value: string) {
        this.value = value;
        this.children = [];
    }
}

const root = new TreeNode('Grandparent');
const parent1 = new TreeNode('Parent1');
const parent2 = new TreeNode('Parent2');
const child1 = new TreeNode('Child1');
const child2 = new TreeNode('Child2');

root.children.push(parent1, parent2);
parent1.children.push(child1, child2);

// Create queue with root node
// Your code here

Hint

Initialize queue as an array with root inside.

3

Traverse the tree using level order BFS

Create an empty array called result to store visited node values. Use a while loop that runs as long as queue.length is greater than 0. Inside the loop, remove the first node from queue using shift() and store it in current. Add current.value to result. Then add all children of current to the end of queue using push(...current.children).

DSA Typescript

class TreeNode {
    value: string;
    children: TreeNode[];
    constructor(value: string) {
        this.value = value;
        this.children = [];
    }
}

const root = new TreeNode('Grandparent');
const parent1 = new TreeNode('Parent1');
const parent2 = new TreeNode('Parent2');
const child1 = new TreeNode('Child1');
const child2 = new TreeNode('Child2');

root.children.push(parent1, parent2);
parent1.children.push(child1, child2);

const queue: TreeNode[] = [root];

// Traverse tree using while loop and queue
// Your code here

Hint

Use shift() to get the first node, add its value to result, then add its children to queue.

4

Print the level order traversal result

Print the result array joined by spaces using console.log(result.join(' ')).

DSA Typescript

class TreeNode {
    value: string;
    children: TreeNode[];
    constructor(value: string) {
        this.value = value;
        this.children = [];
    }
}

const root = new TreeNode('Grandparent');
const parent1 = new TreeNode('Parent1');
const parent2 = new TreeNode('Parent2');
const child1 = new TreeNode('Child1');
const child2 = new TreeNode('Child2');

root.children.push(parent1, parent2);
parent1.children.push(child1, child2);

const queue: TreeNode[] = [root];
const result: string[] = [];

while (queue.length > 0) {
    const current = queue.shift()!;
    result.push(current.value);
    queue.push(...current.children);
}

// Print the result array joined by spaces
// Your code here

Hint

Use console.log(result.join(' ')) to print all node values separated by spaces.

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