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.

Level order traversal for this tree should look like:

- 100
- 50, 200
- 25, 75, 350

- Breadth first traversal

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

// Using two queues void level_order_traversal_1(BinaryTreeNode* root) { if (root == nullptr) { return; } queue<BinaryTreeNode*> queues[2]; queue<BinaryTreeNode*>* current_queue = &queues[0]; queue<BinaryTreeNode*>* next_queue = &queues[1]; current_queue->push(root); int level_number = 0; while (!current_queue->empty()) { BinaryTreeNode* temp = current_queue->front(); current_queue->pop(); cout << temp->data << ","; if (temp->left != nullptr) { next_queue->push(temp->left); } if (temp->right != nullptr) { next_queue->push(temp->right); } if (current_queue->empty()) { cout << endl; ++level_number; current_queue = &queues[level_number % 2]; next_queue = &queues[(level_number + 1) % 2]; } } cout << endl; } int main(int argc, char* argv[]) { BinaryTreeNode* root = create_random_BST(15); level_order_traversal_1(root); cout << endl; cout << "Inorder = "; display_inorder(root); }

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

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

Here, you are using two queues: `current_queue`

and `next_queue`

. You push the nodes in both queues alternately based on the current level number.

You’ll dequeue nodes from the `current_queue`

, print the node’s data, and enqueue the node’s children to the `next_queue`

. Once the `current_queue`

becomes empty, you have processed all nodes for the current `level_number`

. To indicate the new level, print a line break (’\n’), swap the two queues, and continue with the above-mentioned logic.

After printing the leaf nodes from the `current_queue`

, swap `current_queue`

and `next_queue`

. Since the `current_queue`

would be empty, you can terminate the loop.