#include <bits/stdc++.h>
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 two empty queues and enqueue root's left and
// right child respectively
queue<Node *> Q1, Q2;
if(root->left)
Q1.push(root->left);
Q2.push(root->right);
// run till queue is not empty
while (!Q1.empty())
{
// calculate number of nodes in current level
int n = Q1.size();
// process every node of current level
while (n--)
{
// pop front node from first queue and print it
Node* x = Q1.front();
Q1.pop();
cout << x->key << " ";
// push left and right child of x to first queue
if (x->left)
Q1.push(x->left);
if (x->right)
Q1.push(x->right);
// pop front node from second queue and print it
Node* y = Q2.front();
Q2.pop();
cout << y->key << " ";
// push right and left child of y to second queue
if (y->right)
Q2.push(y->right);
if (y->left)
Q2.push(y->left);
}
}
}
// main function
int main()
{
Node* root = nullptr;
vector<pair<string, int> > keys =
{
{"", 1}, {"R", 3}, {"RL", 6},
{"RR", 7}
};
for (auto pair: keys)
insert(root, pair.first, pair.second);
printNodes(root);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBEYXRhIHN0cnVjdHVyZSB0byBzdG9yZSBhIEJpbmFyeSBUcmVlIG5vZGUKc3RydWN0IE5vZGUKewoJaW50IGtleTsKCU5vZGUgKmxlZnQsICpyaWdodDsKfTsKCi8vIEZ1bmN0aW9uIHRvIGNyZWF0ZSBhIG5ldyBiaW5hcnkgdHJlZSBub2RlIGhhdmluZyBnaXZlbiBrZXkKTm9kZSogbmV3Tm9kZShpbnQga2V5KQp7CglOb2RlKiBub2RlID0gbmV3IE5vZGU7Cglub2RlLT5rZXkgPSBrZXk7Cglub2RlLT5sZWZ0ID0gbm9kZS0+cmlnaHQgPSBudWxscHRyOwoKCXJldHVybiBub2RlOwp9CgovLyBGdW5jdGlvbiB0byBpbnNlcnQgZ2l2ZW4ga2V5IGludG8gdGhlIHRyZWUKdm9pZCBpbnNlcnQoTm9kZSomIHJvb3QsIHN0cmluZyBsZXZlbCwgaW50IGtleSkKewoJLy8gdHJlZSBpcyBlbXB0eQoJaWYgKGxldmVsLmxlbmd0aCgpID09IDApCgl7CgkJcm9vdCA9IG5ld05vZGUoa2V5KTsKCQlyZXR1cm47Cgl9CgoJaW50IGkgPSAwOwoJTm9kZSogcHRyID0gcm9vdDsKCXdoaWxlIChpIDwgbGV2ZWwubGVuZ3RoKCkgLSAxKQoJewoJCWlmIChsZXZlbFtpKytdID09ICdMJykKCQkJcHRyID0gcHRyLT5sZWZ0OwoJCWVsc2UKCQkJcHRyID0gcHRyLT5yaWdodDsKCX0KCglpZiAobGV2ZWxbaV0gPT0gJ0wnKQoJCXB0ci0+bGVmdCA9IG5ld05vZGUoa2V5KTsKCWVsc2UKCQlwdHItPnJpZ2h0ID0gbmV3Tm9kZShrZXkpOwp9CgovLyBGdW5jdGlvbiB0byBwcmludCBhbGwgbm9kZXMgb2YgYSBnaXZlbiBiaW5hcnkgdHJlZSBpbiBzcGVjaWZpYwovLyBvcmRlciBmcm9tIHRvcCB0byBib3R0b20Kdm9pZCBwcmludE5vZGVzKE5vZGUqIHJvb3QpCnsKICAgIC8vIHJldHVybiBpcyB0cmVlIGlzIGVtcHR5CglpZiAocm9vdCA9PSBudWxscHRyKQoJCXJldHVybjsKCiAgICAvLyBwcmludCByb290IG5vZGUKCWNvdXQgPDwgcm9vdC0+a2V5IDw8ICIgIjsKCiAgICAvLyBjcmVhdGUgYW4gdHdvIGVtcHR5IHF1ZXVlcyBhbmQgZW5xdWV1ZSByb290J3MgbGVmdCBhbmQKICAgIC8vIHJpZ2h0IGNoaWxkIHJlc3BlY3RpdmVseQoJcXVldWU8Tm9kZSAqPiBRMSwgUTI7CglpZihyb290LT5sZWZ0KQoJCVExLnB1c2gocm9vdC0+bGVmdCk7CglRMi5wdXNoKHJvb3QtPnJpZ2h0KTsKCiAgICAvLyBydW4gdGlsbCBxdWV1ZSBpcyBub3QgZW1wdHkKCXdoaWxlICghUTEuZW1wdHkoKSkKCXsKCQkvLyBjYWxjdWxhdGUgbnVtYmVyIG9mIG5vZGVzIGluIGN1cnJlbnQgbGV2ZWwKCQlpbnQgbiA9IFExLnNpemUoKTsKCgkJLy8gcHJvY2VzcyBldmVyeSBub2RlIG9mIGN1cnJlbnQgbGV2ZWwKCQl3aGlsZSAobi0tKQoJCXsKCQkgICAgLy8gcG9wIGZyb250IG5vZGUgZnJvbSBmaXJzdCBxdWV1ZSBhbmQgcHJpbnQgaXQKCQkJTm9kZSogeCA9IFExLmZyb250KCk7CgkJCVExLnBvcCgpOwoKCQkJY291dCA8PCB4LT5rZXkgPDwgIiAiOwoKCQkJLy8gcHVzaCBsZWZ0IGFuZCByaWdodCBjaGlsZCBvZiB4IHRvIGZpcnN0IHF1ZXVlCgkJCWlmICh4LT5sZWZ0KQoJCQkJUTEucHVzaCh4LT5sZWZ0KTsKCgkJCWlmICh4LT5yaWdodCkKCQkJCVExLnB1c2goeC0+cmlnaHQpOwoKCgkJICAgIC8vIHBvcCBmcm9udCBub2RlIGZyb20gc2Vjb25kIHF1ZXVlIGFuZCBwcmludCBpdAoJCQlOb2RlKiB5ID0gUTIuZnJvbnQoKTsKICAgICAgICAgICAgUTIucG9wKCk7CgoJCQljb3V0IDw8IHktPmtleSA8PCAiICI7CgoJCQkvLyBwdXNoIHJpZ2h0IGFuZCBsZWZ0IGNoaWxkIG9mIHkgdG8gc2Vjb25kIHF1ZXVlCgkJCWlmICh5LT5yaWdodCkKCQkJCVEyLnB1c2goeS0+cmlnaHQpOwoKCQkJaWYgKHktPmxlZnQpCgkJCQlRMi5wdXNoKHktPmxlZnQpOwoJCX0KCX0KfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbigpCnsKCU5vZGUqIHJvb3QgPSBudWxscHRyOwoJdmVjdG9yPHBhaXI8c3RyaW5nLCBpbnQ+ID4ga2V5cyA9Cgl7CgkJeyIiLCAxfSwgeyJSIiwgM30sIHsiUkwiLCA2fSwKCQl7IlJSIiwgN30KCX07CgoJZm9yIChhdXRvIHBhaXI6IGtleXMpCgkJaW5zZXJ0KHJvb3QsIHBhaXIuZmlyc3QsIHBhaXIuc2Vjb25kKTsKCglwcmludE5vZGVzKHJvb3QpOwoKCXJldHVybiAwOwp9Cg==