// Time Complexity : O(n)
// Space Complexity : O(n)
#include <iostream>
#include <vector>
#include <queue>
#include <map>
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;
// start with level 1 (of root node)
int level = 1;
// create an empty multi-map of integers (every key can be
// associated with multiple values)
map<int, vector<int>> map;
// insert root node at first level
map[level].push_back(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())
{
// increment level by 1
level++;
// calculate number of nodes in current level
int n = Q.size();
while (n)
{
// pop first two nodes from queue and insert them into the map
Node* x = Q.front();
Q.pop();
Node* y = Q.front();
Q.pop();
map[level].push_back(x->key);
map[level].push_back(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);
n = n - 2;
}
}
// iterate through the map using reverse iterator and
// print all nodes present in very level
for (auto it = map.rbegin(); it != map.rend(); it++)
{
for (int i: it->second)
cout << i << " ";
}
}
// 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+CiNpbmNsdWRlIDxtYXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBEYXRhIHN0cnVjdHVyZSB0byBzdG9yZSBhIEJpbmFyeSBUcmVlIG5vZGUKc3RydWN0IE5vZGUKewoJaW50IGtleTsKCU5vZGUgKmxlZnQsICpyaWdodDsKfTsKCi8vIEZ1bmN0aW9uIHRvIGNyZWF0ZSBhIG5ldyBiaW5hcnkgdHJlZSBub2RlIGhhdmluZyBnaXZlbiBrZXkKTm9kZSogbmV3Tm9kZShpbnQga2V5KQp7CglOb2RlKiBub2RlID0gbmV3IE5vZGU7Cglub2RlLT5rZXkgPSBrZXk7Cglub2RlLT5sZWZ0ID0gbm9kZS0+cmlnaHQgPSBudWxscHRyOwoKCXJldHVybiBub2RlOwp9CgovLyBGdW5jdGlvbiB0byBpbnNlcnQgZ2l2ZW4ga2V5IGludG8gdGhlIHRyZWUKdm9pZCBpbnNlcnQoTm9kZSomIHJvb3QsIHN0cmluZyBsZXZlbCwgaW50IGtleSkKewoJLy8gdHJlZSBpcyBlbXB0eQoJaWYgKGxldmVsLmxlbmd0aCgpID09IDApCgl7CgkJcm9vdCA9IG5ld05vZGUoa2V5KTsKCQlyZXR1cm47Cgl9CgoJaW50IGkgPSAwOwoJTm9kZSogcHRyID0gcm9vdDsKCXdoaWxlIChpIDwgbGV2ZWwubGVuZ3RoKCkgLSAxKQoJewoJCWlmIChsZXZlbFtpKytdID09ICdMJykKCQkJcHRyID0gcHRyLT5sZWZ0OwoJCWVsc2UKCQkJcHRyID0gcHRyLT5yaWdodDsKCX0KCglpZiAobGV2ZWxbaV0gPT0gJ0wnKQoJCXB0ci0+bGVmdCA9IG5ld05vZGUoa2V5KTsKCWVsc2UKCQlwdHItPnJpZ2h0ID0gbmV3Tm9kZShrZXkpOwp9CgovLyBGdW5jdGlvbiB0byBwcmludCBhbGwgbm9kZXMgb2YgYSBnaXZlbiBiaW5hcnkgdHJlZSBpbiBzcGVjaWZpYwovLyBvcmRlciBmcm9tIHRvcCB0byBib3R0b20Kdm9pZCBwcmludE5vZGVzKE5vZGUqIHJvb3QpCnsKICAgIC8vIHJldHVybiBpcyB0cmVlIGlzIGVtcHR5CglpZiAocm9vdCA9PSBudWxscHRyKQoJCXJldHVybjsKCiAgICAvLyBzdGFydCB3aXRoIGxldmVsIDEgKG9mIHJvb3Qgbm9kZSkKCWludCBsZXZlbCA9IDE7CgoJLy8gY3JlYXRlIGFuIGVtcHR5IG11bHRpLW1hcCBvZiBpbnRlZ2VycyAoZXZlcnkga2V5IGNhbiBiZQogICAgLy8gYXNzb2NpYXRlZCB3aXRoIG11bHRpcGxlIHZhbHVlcykKICAgIG1hcDxpbnQsIHZlY3RvcjxpbnQ+PiBtYXA7CgogICAgLy8gaW5zZXJ0IHJvb3Qgbm9kZSBhdCBmaXJzdCBsZXZlbAoJbWFwW2xldmVsXS5wdXNoX2JhY2socm9vdC0+a2V5KTsKCiAgICAvLyBjcmVhdGUgYW4gZW1wdHkgcXVldWUgYW5kIGVucXVldWUgcm9vdCdzIGxlZnQgYW5kCiAgICAvLyByaWdodCBjaGlsZCByZXNwZWN0aXZlbHkKCXF1ZXVlPE5vZGUgKj4gUTsKCQoJaWYocm9vdC0+bGVmdCAmJiByb290LT5yaWdodCkKCXsKCQlRLnB1c2gocm9vdC0+bGVmdCk7CgkJUS5wdXNoKHJvb3QtPnJpZ2h0KTsKCX0KCiAgICAvLyBydW4gdGlsbCBxdWV1ZSBpcyBub3QgZW1wdHkKCXdoaWxlICghUS5lbXB0eSgpKQoJewoJCS8vIGluY3JlbWVudCBsZXZlbCBieSAxCgkJbGV2ZWwrKzsKCgkJLy8gY2FsY3VsYXRlIG51bWJlciBvZiBub2RlcyBpbiBjdXJyZW50IGxldmVsCgkJaW50IG4gPSBRLnNpemUoKTsKCQkKCQl3aGlsZSAobikKCQl7CgkJCS8vIHBvcCBmaXJzdCB0d28gbm9kZXMgZnJvbSBxdWV1ZSBhbmQgaW5zZXJ0IHRoZW0gaW50byB0aGUgbWFwCgkJCU5vZGUqIHggPSBRLmZyb250KCk7CgkJCVEucG9wKCk7CgoJCQlOb2RlKiB5ID0gUS5mcm9udCgpOwoJCSAgICBRLnBvcCgpOwoKCQkJbWFwW2xldmVsXS5wdXNoX2JhY2soeC0+a2V5KTsKCQkJbWFwW2xldmVsXS5wdXNoX2JhY2soeS0+a2V5KTsKCgkJCS8vIEluIGVhY2ggaXRlcmF0aW9uIGVucXVldWUgeC0+bGVmdCwgeS0+cmlnaHQgdGhlbiB4LT5yaWdodCwgeS0+bGVmdCAKCQkJaWYgKHgtPmxlZnQpCgkJCQlRLnB1c2goeC0+bGVmdCk7CgoJCQlpZiAoeS0+cmlnaHQpCgkJCQlRLnB1c2goeS0+cmlnaHQpOwoKCQkJaWYgKHgtPnJpZ2h0KQoJCQkJUS5wdXNoKHgtPnJpZ2h0KTsKCgkJCWlmICh5LT5sZWZ0KQoJCQkJUS5wdXNoKHktPmxlZnQpOwoKCQkJbiA9IG4gLSAyOwoJCX0KCX0KCiAgICAvLyBpdGVyYXRlIHRocm91Z2ggdGhlIG1hcCB1c2luZyByZXZlcnNlIGl0ZXJhdG9yIGFuZAoJLy8gcHJpbnQgYWxsIG5vZGVzIHByZXNlbnQgaW4gdmVyeSBsZXZlbAoJZm9yIChhdXRvIGl0ID0gbWFwLnJiZWdpbigpOyBpdCAhPSBtYXAucmVuZCgpOyBpdCsrKQoJewoJCWZvciAoaW50IGk6IGl0LT5zZWNvbmQpCgkJCWNvdXQgPDwgaSA8PCAiICI7Cgl9Cn0KCi8vIG1haW4gZnVuY3Rpb24KaW50IG1haW4oKQp7CglOb2RlKiByb290ID0gbnVsbHB0cjsKCXZlY3RvcjxwYWlyPHN0cmluZywgaW50PiA+IGtleXMgPQoJewoJCXsiIiwgMX0sIHsiTCIsIDJ9LCB7IlIiLCAzfSwgeyJMTCIsIDR9LCB7IkxSIiwgNX0sIHsiUkwiLCA2fSwKCQl7IlJSIiwgN30sIHsiTExMIiwgOH0sIHsiTExSIiwgOX0sIHsiTFJMIiwgMTB9LCB7IkxSUiIsIDExfSwKCQl7IlJMTCIsIDEyfSwgeyJSTFIiLCAxM30sIHsiUlJMIiwgMTR9LCB7IlJSUiIsIDE1fQoJfTsKCglmb3IgKGF1dG8gcGFpcjoga2V5cykKCQlpbnNlcnQocm9vdCwgcGFpci5maXJzdCwgcGFpci5zZWNvbmQpOwoKCXByaW50Tm9kZXMocm9vdCk7CgoJcmV0dXJuIDA7Cn0K