// Time Complexity : O(n)
// Space Complexity : O(n)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a Binary Tree node
struct Node
{
int key;
Node *left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = nullptr;
return node;
}
// Function to insert given key into the tree
void insert(Node*& root, string level, int key)
{
// tree is empty
if (level.length() == 0)
{
root = newNode(key);
return;
}
int i = 0;
Node* ptr = root;
while (i < level.length() - 1)
{
if (level[i++] == 'L')
ptr = ptr->left;
else
ptr = ptr->right;
}
if (level[i] == 'L')
ptr->left = newNode(key);
else
ptr->right = newNode(key);
}
// Function to print all nodes of a given binary tree in specific
// order from top to bottom
void printNodes(Node* root)
{
// return is tree is empty
if (root == nullptr)
return;
// print root node
cout << root->key << " ";
// create an empty queue and enqueue root's left and
// right child respectively
queue<Node *> Q;
if(root->left && root->right)
{
Q.push(root->left);
Q.push(root->right);
}
// run till queue is not empty
while (!Q.empty())
{
Node* x = Q.front();
Q.pop();
Node* y = Q.front();
Q.pop();
cout << x->key << " ";
cout << y->key << " ";
// In each iteration enqueue x->left, y->right then x->right, y->left
if (x->left)
Q.push(x->left);
if (y->right)
Q.push(y->right);
if (x->right)
Q.push(x->right);
if (y->left)
Q.push(y->left);
}
}
// main function
int main()
{
Node* root = nullptr;
vector<pair<string, int> > keys =
{
{"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"LR", 5}, {"RL", 6},
{"RR", 7}, {"LLL", 8}, {"LLR", 9}, {"LRL", 10}, {"LRR", 11},
{"RLL", 12}, {"RLR", 13}, {"RRL", 14}, {"RRR", 15}
};
for (auto pair: keys)
insert(root, pair.first, pair.second);
printNodes(root);
return 0;
}
Ly8gVGltZSBDb21wbGV4aXR5IDogTyhuKQovLyBTcGFjZSBDb21wbGV4aXR5IDogTyhuKQoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBEYXRhIHN0cnVjdHVyZSB0byBzdG9yZSBhIEJpbmFyeSBUcmVlIG5vZGUKc3RydWN0IE5vZGUKewoJaW50IGtleTsKCU5vZGUgKmxlZnQsICpyaWdodDsKfTsKCi8vIEZ1bmN0aW9uIHRvIGNyZWF0ZSBhIG5ldyBiaW5hcnkgdHJlZSBub2RlIGhhdmluZyBnaXZlbiBrZXkKTm9kZSogbmV3Tm9kZShpbnQga2V5KQp7CglOb2RlKiBub2RlID0gbmV3IE5vZGU7Cglub2RlLT5rZXkgPSBrZXk7Cglub2RlLT5sZWZ0ID0gbm9kZS0+cmlnaHQgPSBudWxscHRyOwoKCXJldHVybiBub2RlOwp9CgovLyBGdW5jdGlvbiB0byBpbnNlcnQgZ2l2ZW4ga2V5IGludG8gdGhlIHRyZWUKdm9pZCBpbnNlcnQoTm9kZSomIHJvb3QsIHN0cmluZyBsZXZlbCwgaW50IGtleSkKewoJLy8gdHJlZSBpcyBlbXB0eQoJaWYgKGxldmVsLmxlbmd0aCgpID09IDApCgl7CgkJcm9vdCA9IG5ld05vZGUoa2V5KTsKCQlyZXR1cm47Cgl9CgoJaW50IGkgPSAwOwoJTm9kZSogcHRyID0gcm9vdDsKCXdoaWxlIChpIDwgbGV2ZWwubGVuZ3RoKCkgLSAxKQoJewoJCWlmIChsZXZlbFtpKytdID09ICdMJykKCQkJcHRyID0gcHRyLT5sZWZ0OwoJCWVsc2UKCQkJcHRyID0gcHRyLT5yaWdodDsKCX0KCglpZiAobGV2ZWxbaV0gPT0gJ0wnKQoJCXB0ci0+bGVmdCA9IG5ld05vZGUoa2V5KTsKCWVsc2UKCQlwdHItPnJpZ2h0ID0gbmV3Tm9kZShrZXkpOwp9CgovLyBGdW5jdGlvbiB0byBwcmludCBhbGwgbm9kZXMgb2YgYSBnaXZlbiBiaW5hcnkgdHJlZSBpbiBzcGVjaWZpYwovLyBvcmRlciBmcm9tIHRvcCB0byBib3R0b20Kdm9pZCBwcmludE5vZGVzKE5vZGUqIHJvb3QpCnsKICAgIC8vIHJldHVybiBpcyB0cmVlIGlzIGVtcHR5CglpZiAocm9vdCA9PSBudWxscHRyKQoJCXJldHVybjsKCiAgICAvLyBwcmludCByb290IG5vZGUKCWNvdXQgPDwgcm9vdC0+a2V5IDw8ICIgIjsKCiAgICAvLyBjcmVhdGUgYW4gZW1wdHkgcXVldWUgYW5kIGVucXVldWUgcm9vdCdzIGxlZnQgYW5kCiAgICAvLyByaWdodCBjaGlsZCByZXNwZWN0aXZlbHkKCXF1ZXVlPE5vZGUgKj4gUTsKCQoJaWYocm9vdC0+bGVmdCAmJiByb290LT5yaWdodCkKCXsKCQlRLnB1c2gocm9vdC0+bGVmdCk7CgkJUS5wdXNoKHJvb3QtPnJpZ2h0KTsKCX0KCiAgICAvLyBydW4gdGlsbCBxdWV1ZSBpcyBub3QgZW1wdHkKCXdoaWxlICghUS5lbXB0eSgpKQoJewoJCU5vZGUqIHggPSBRLmZyb250KCk7CgkJUS5wb3AoKTsKCgkJTm9kZSogeSA9IFEuZnJvbnQoKTsKICAgICAgICBRLnBvcCgpOwoKCQljb3V0IDw8IHgtPmtleSA8PCAiICI7CgkJY291dCA8PCB5LT5rZXkgPDwgIiAiOwoKCQkvLyBJbiBlYWNoIGl0ZXJhdGlvbiBlbnF1ZXVlIHgtPmxlZnQsIHktPnJpZ2h0IHRoZW4geC0+cmlnaHQsIHktPmxlZnQgCgkJaWYgKHgtPmxlZnQpCgkJCVEucHVzaCh4LT5sZWZ0KTsKCgkJaWYgKHktPnJpZ2h0KQoJCQlRLnB1c2goeS0+cmlnaHQpOwoKCQlpZiAoeC0+cmlnaHQpCgkJCVEucHVzaCh4LT5yaWdodCk7CgoJCWlmICh5LT5sZWZ0KQoJCQlRLnB1c2goeS0+bGVmdCk7Cgl9Cn0KCi8vIG1haW4gZnVuY3Rpb24KaW50IG1haW4oKQp7CglOb2RlKiByb290ID0gbnVsbHB0cjsKCXZlY3RvcjxwYWlyPHN0cmluZywgaW50PiA+IGtleXMgPQoJewoJCXsiIiwgMX0sIHsiTCIsIDJ9LCB7IlIiLCAzfSwgeyJMTCIsIDR9LCB7IkxSIiwgNX0sIHsiUkwiLCA2fSwKCQl7IlJSIiwgN30sIHsiTExMIiwgOH0sIHsiTExSIiwgOX0sIHsiTFJMIiwgMTB9LCB7IkxSUiIsIDExfSwKCQl7IlJMTCIsIDEyfSwgeyJSTFIiLCAxM30sIHsiUlJMIiwgMTR9LCB7IlJSUiIsIDE1fQoJfTsKCglmb3IgKGF1dG8gcGFpcjoga2V5cykKCQlpbnNlcnQocm9vdCwgcGFpci5maXJzdCwgcGFpci5zZWNvbmQpOwoKCXByaW50Tm9kZXMocm9vdCk7CgoJcmV0dXJuIDA7Cn0K