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.