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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Level Order Traversal on a Simple Binary Tree

What is the output of the following C++ code performing level order traversal (BFS) on the given binary tree?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> levelOrder(Node* root) {
    std::vector<int> result;
    if (!root) return result;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

int main() {
    Node* 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);
    std::vector<int> output = levelOrder(root);
    for (int v : output) std::cout << v << " ";
    return 0;
}

A 2 3 1 4 5

B 1 3 2 5 4

C 4 5 2 3 1

D 1 2 3 4 5

💡 Hint

Remember, level order traversal visits nodes level by level from left to right.

The code uses a queue to visit nodes level by level. Starting from root (1), then its children (2, 3), then their children (4, 5). So output is 1 2 3 4 5.

🧠 Conceptual

intermediate

Number of Levels in Level Order Traversal

Given a binary tree, how many levels will the level order traversal visit for the tree below? Tree structure: - Root node 10 - Left child 20 - Right child 30 - Left child of 20 is 40 - Right child of 20 is 50 - Left child of 30 is 60

A 5

B 3

C 4

D 2

💡 Hint

Count the levels from root down to the deepest leaf.

The tree has root level (10), second level (20, 30), and third level (40, 50, 60). So total 3 levels.

🔧 Debug

advanced

Identify the Bug in Level Order Traversal Code

What error will the following C++ code produce when performing level order traversal?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> levelOrder(Node* root) {
    std::vector<int> result;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

int main() {
    Node* root = nullptr;
    std::vector<int> output = levelOrder(root);
    for (int v : output) std::cout << v << " ";
    return 0;
}

A Segmentation fault (runtime error)

B Empty output (no values printed)

C Compilation error due to missing header

D Infinite loop

💡 Hint

Check what happens when root is nullptr but still pushed into the queue.

The code pushes nullptr into the queue without checking if root is null. Then accessing node->val causes segmentation fault.

📝 Syntax

advanced

Syntax Error in Level Order Traversal Code

Which option contains the correct syntax to push children nodes into the queue during level order traversal?

DSA C++

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);

A if node->left { q.push(node->left); } if node->right { q.push(node->right); }

B if node->left q.push(node->left); if node->right q.push(node->right);

C if (node->left) q.push(node->left); if (node->right) q.push(node->right);

D if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); }

💡 Hint

Remember C++ requires parentheses around conditions and semicolons after statements.

Option C uses correct C++ syntax with parentheses and semicolons. Others miss parentheses or semicolons causing syntax errors.

🚀 Application

expert

Level Order Traversal Output After Node Insertions

Given an initially empty binary tree, nodes are inserted in this order: 1. Insert 10 as root 2. Insert 20 as left child of 10 3. Insert 30 as right child of 10 4. Insert 40 as left child of 20 5. Insert 50 as right child of 20 6. Insert 60 as left child of 30 What is the output of the level order traversal after all insertions?

A 10 20 30 40 50 60

B 20 10 30 40 50 60

C 40 50 60 20 30 10

D 10 30 20 60 50 40

💡 Hint

Level order visits nodes level by level from left to right.

The tree levels are: Level 1: 10 Level 2: 20, 30 Level 3: 40, 50, 60 So output is 10 20 30 40 50 60.