Level Order Traversal of Binary Tree

Level Order Traversal of Binary Tree

1 min read
Oct 15, 2025
Share
editor-page-cover
Content
Problem Statement
Hint
Try it yourself
Solution
Solution Explanation
Runtime Complexity
Memory Complexity
Solution Breakdown

Problem Statement#

Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.


widget

Level order traversal for this tree should look like: 100; 50, 200; 25, 75, 350

Hint#

  • Breadth first traversal

Try it yourself#

string levelOrderTraversal(BinaryTreeNode* root) {
string result = "";
//TODO: Write - Your - Code
return result;
}

Solution#

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <sstream>
std::string levelOrderTraversal(BinaryTreeNode* root) {
if (root == nullptr) {
return "None";
}
std::vector<std::string> result;
std::deque<BinaryTreeNode*> queue;
queue.push_back(root);
while (!queue.empty()) {
int levelSize = queue.size();
std::vector<std::string> levelNodes;
for (int i = 0; i < levelSize; ++i) {
BinaryTreeNode* temp = queue.front();
queue.pop_front();
levelNodes.push_back(std::to_string(temp->data));
if (temp->left != nullptr) {
queue.push_back(temp->left);
}
if (temp->right != nullptr) {
queue.push_back(temp->right);
}
}
std::ostringstream oss;
for (size_t i = 0; i < levelNodes.size(); ++i) {
if (i != 0) oss << ", ";
oss << levelNodes[i];
}
result.push_back(oss.str());
}
std::ostringstream oss;
for (size_t i = 0; i < result.size(); ++i) {
if (i != 0) oss << "; ";
oss << result[i];
}
return oss.str();
}
int main(int argc, char* argv[]) {
BinaryTreeNode* root = create_random_BST(15);
cout << endl;
cout << "Inorder = ";
display_inorder(root);
cout << "\nLevel order = ";
cout<< levelOrderTraversal(root);
}

Solution Explanation#

Runtime Complexity#

The runtime complexity of this solution is linear, O(n)O(n).

Memory Complexity#

The memory complexity of this solution is linear, O(n)O(n).

Solution Breakdown#

  1. Initialize a queue, queue, with the root node.

  2. Iterate over the queue until it’s empty:

    1. For each level, calculate the size (level_size) of the queue.

    2. Initialize an empty list level_nodes.

    3. Iterate level_size times:

      1. Dequeue a node from the queue.

      2. Append the value of the dequeued node in level_nodes.

      3. Enqueue the left child and the right child of the dequeued node in queue, if they exist.

    4. Convert level_nodes to a comma-separated string and store it in result.

  3. Return the result.

Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!


Written By:
Zarish Khalid
New on Educative
Learn to Code
Learn any Language as a beginner
Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog
🎁 G i v e a w a y
30 Days of Code
Complete Educative’s daily coding challenge every day in September, and win exciting Prizes.