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:
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.