Print Each Level of a Binary Tree in C++

To print each level of a binary tree on a separate line in C++, you can use a Breadth-First Search (BFS) algorithm with a queue. By tracking the number of nodes at the current level, you can iterate through the queue, pop the nodes, print their values, and push their children. A newline is printed after each level is fully processed.

Someone important on X posted:

https://x.com/vikhyatk/status/1873033432705712304

i have a very simple question i ask during phone screens: print each level of a tree on a separate line. 90% of CS grad candidates just can't do it. someone needs to investigate these universities.

half the replies are saying i'm trolling because no one asks questions this simple. the other half are saying it's a retarded leetcode question, they never have to use trees irl, why is it even relevant because ChatGPT can do it etc.

Solution with Boost Library

#include <boost/property_tree/ptree.hpp>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

void levelOrder(const boost::property_tree::ptree& tree) {
    std::queue<boost::property_tree::ptree> q;
    q.push(tree);

    while (!q.empty()) {
        int levelSize = q.size();
        while (levelSize > 0) {
            boost::property_tree::ptree current = q.front();
            q.pop();

            auto val = current.get_value<std::string>("");
            if (val != "")
                std::cout << current.get_value<std::string>("")<<" ";

            for (const auto& node : current) {
                q.push(node.second);
            }
            --levelSize;
        }
        std::cout << std::endl;
    }
}

int main() {
    boost::property_tree::ptree tree;
    tree.put("root.value", "10");
    tree.put("root.left.value", "5");
    tree.put("root.left.left.value", "3");
    tree.put("root.left.right.value", "7");
    tree.put("root.right.value", "15");
    tree.put("root.right.right.value", "20");
    levelOrder(tree);
    return 0;
}

So I wanted to try out using Boost with CLion. What a nightmare. First the issue of using a flatpak install ruins everything when it comes to integrating with the system.

Second using a property tree was a bad idea. I should have went with a graph. Since the original post on X was talking about the solution with a graphic of a binary tree, I tried the property_tree in boost and I didn't like the output of the tree still, nor the key value pair structure of it.

I will follow up later with a Breadth First Search on an Undirected Graph from Boost library next time.

Understanding the Level Order Traversal Concept

The problem of printing each level of a tree on a separate line is fundamentally an exercise in breadth-first search (BFS). While depth-first search algorithms like in-order, pre-order, or post-order traversal explore as deeply as possible along each branch before backtracking, BFS explores the neighbor nodes first, before moving to the next level neighbors.

In standard C++ implementations, we typically define a custom tree node structure rather than relying on external libraries like Boost. Using a standard std::queue from the C++ Standard Template Library (STL) provides the most efficient and straightforward path to success in coding interviews.

Why Do Candidates Fail This Interview Question?

The high failure rate among computer science graduates when faced with this specific binary tree traversal problem often stems from a lack of practical algorithm implementation during their studies. Many students memorize theoretical concepts but struggle to translate them into working code, especially under the pressure of a technical screening.

Frequently Asked Questions