Tree Traversal Level Order BFS in DSA C++ - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: You work at a company that manages family trees. You need to show family members level by level, starting from the oldest ancestor.

🎯 Goal: Build a program that creates a simple family tree and prints the names of family members level by level using Breadth-First Search (BFS).

📋 What You'll Learn

Create a struct Node for tree nodes with string name, Node* left, and Node* right.

Create the family tree with exact names and structure.

Use a queue to perform level order traversal (BFS).

Print the names in level order separated by spaces.

💡 Why This Matters

🌍 Real World

Level order traversal is used in family trees, organizational charts, and network broadcasting to visit nodes level by level.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with hierarchical data and algorithms.

1

Create the Node struct and family tree

Create a struct Node with string name, Node* left, and Node* right. Then create the family tree with root named "Grandpa", left child "Dad", right child "Uncle", and "Dad" has left child "Me" and right child "Sister".

DSA C++

// Define struct Node
// Create nodes and link them to form the family tree

Hint

Define the Node struct with a constructor. Then create nodes and connect them as described.

2

Include queue and prepare for BFS

Include the <queue> header and create a queue<Node*> named q to help with level order traversal. Push the root node into q.

DSA C++

#include 
// Create queue q
// Push root into q
// Your code here

Hint

Remember to include <queue> and create a queue of Node*. Then push the root node into it.

3

Implement the level order traversal loop

Use a while loop that runs while q is not empty. Inside the loop, get the front node from q into Node* current, then pop it from q. Print current->name followed by a space. If current->left is not nullptr, push it into q. If current->right is not nullptr, push it into q.

DSA C++

// Use while loop with condition !q.empty()
// Inside loop: Node* current = q.front(); q.pop();
// Print current->name and a space
// If current->left != nullptr, push it to q
// If current->right != nullptr, push it to q
// Your code here

Hint

Use a queue to visit nodes level by level. Print the name and add children to the queue.

4

Print the final level order traversal output

Add a cout statement to print a newline character \n after the level order traversal loop to end the output cleanly.

DSA C++

// Print a newline after the traversal
// Your code here

Hint

After printing all names with spaces, print a newline to finish the output.