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.
string levelOrderTraversal(BinaryTreeNode* root) {string result = "";//TODO: Write - Your - Codereturn result;}
#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);}
The runtime complexity of this solution is linear, O(n)O(n).
The memory complexity of this solution is linear, O(n)O(n).
Initialize a queue, queue
, with the root node.
Iterate over the queue
until it’s empty:
For each level, calculate the size (level_size)
of the queue.
Initialize an empty list level_nodes
.
Iterate level_size
times:
Dequeue a node from the queue
.
Append the value of the dequeued node in level_nodes
.
Enqueue the left child and the right child of the dequeued node in queue
, if they exist.
Convert level_nodes
to a comma-separated string and store it in result
.
Return the result
.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!