#include <bits/stdc++.h>
using namespace std;
// Data structure to store a Binary Tree node
struct Node
{
int data;
Node *left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
Node* node = new Node;
node->data = 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 check if given node is a leaf node or not
bool isLeaf(Node* node)
{
return (node->left == nullptr && node->right == nullptr);
}
// Recursive function to print root-to-leaf path for a given leaf
void printPathRecursive(Node* curr, unordered_map<Node*, Node*> map)
{
// base case : curr is root node (parent of root node is null)
if (curr == nullptr)
return;
// recursively call parent node
printPathRecursive(map[curr], map);
cout << curr->data << (isLeaf(curr) ? "\n" : " -> ");
}
// Iterative function to print leaf-to-root path for a given leaf
// For printing root-to-leaf path, we can use printPathRecursive() or a stack
void printPathIterative(Node* leafNode, unordered_map<Node*, Node*> map)
{
// start from the leaf node
Node* curr = leafNode;
// loop till root node is reached and print each node in the path
while (map[curr] != nullptr)
{
cout << curr->data << " -> ";
curr = map[curr];
}
cout << curr->data << endl;
}
// Iterative function to perform in-order traversal of the tree
void inorderIterative(Node *root)
{
// create an empty stack
stack<Node*> stack;
// map (child, parent)
unordered_map<Node*, Node*> map;
// parent of root node is null
map[root] = nullptr;
// start from root node (set current node to root node)
Node *curr = root;
// if current node is null and stack is also empty, we're done
while (!stack.empty() || curr != nullptr)
{
// if current node is not null, push it to the stack (defer it)
// and move to its left child
if (curr != nullptr)
{
stack.push(curr);
// include current node left and right child in a map
if (curr->left)
map[curr->left] = curr;
if (curr->right)
map[curr->right] = curr;
curr = curr->left;
}
else
{
// else if current node is null, we pop an element from the stack,
// print it and finally set current node to its right child
curr = stack.top();
stack.pop();
// if leaf node is found, print the path
if (isLeaf(curr))
{
// print leaf-to-root path for current leaf
printPathIterative(curr, map);
// print root-to-leaf path for current leaf
// printPathRecursive(curr, map);
}
curr = curr->right;
}
}
}
// main function
int main()
{
/* Construct below tree
1
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
/ \
/ \
8 9
*/
vector<pair<string, int>> keys =
{
{"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"LR", 5}, {"RL", 6},
{"RR", 7}, {"RLL", 8}, {"RLR", 9}
};
Node* root = nullptr;
for (auto pair: keys)
insert(root, pair.first, pair.second);
inorderIterative(root);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBEYXRhIHN0cnVjdHVyZSB0byBzdG9yZSBhIEJpbmFyeSBUcmVlIG5vZGUKc3RydWN0IE5vZGUKewogICAgaW50IGRhdGE7CiAgICBOb2RlICpsZWZ0LCAqcmlnaHQ7Cn07CgovLyBGdW5jdGlvbiB0byBjcmVhdGUgYSBuZXcgYmluYXJ5IHRyZWUgbm9kZSBoYXZpbmcgZ2l2ZW4ga2V5Ck5vZGUqIG5ld05vZGUoaW50IGtleSkKewogICAgTm9kZSogbm9kZSA9IG5ldyBOb2RlOwogICAgbm9kZS0+ZGF0YSA9IGtleTsKICAgIG5vZGUtPmxlZnQgPSBub2RlLT5yaWdodCA9IG51bGxwdHI7CgogICAgcmV0dXJuIG5vZGU7Cn0KCi8vIEZ1bmN0aW9uIHRvIGluc2VydCBnaXZlbiBrZXkgaW50byB0aGUgdHJlZQp2b2lkIGluc2VydChOb2RlKiYgcm9vdCwgc3RyaW5nIGxldmVsLCBpbnQga2V5KQp7CiAgICAvLyB0cmVlIGlzIGVtcHR5CiAgICBpZiAobGV2ZWwubGVuZ3RoKCkgPT0gMCkKICAgIHsKICAgICAgICByb290ID0gbmV3Tm9kZShrZXkpOwogICAgICAgIHJldHVybjsKICAgIH0KCiAgICBpbnQgaSA9IDA7CiAgICBOb2RlKiBwdHIgPSByb290OwogICAgd2hpbGUgKGkgPCBsZXZlbC5sZW5ndGgoKSAtIDEpCiAgICB7CiAgICAgICAgaWYgKGxldmVsW2krK10gPT0gJ0wnKQogICAgICAgICAgICBwdHIgPSBwdHItPmxlZnQ7CiAgICAgICAgZWxzZQogICAgICAgICAgICBwdHIgPSBwdHItPnJpZ2h0OwogICAgfQoKICAgIGlmIChsZXZlbFtpXSA9PSAnTCcpCiAgICAgICAgcHRyLT5sZWZ0ID0gbmV3Tm9kZShrZXkpOwogICAgZWxzZQogICAgICAgIHB0ci0+cmlnaHQgPSBuZXdOb2RlKGtleSk7Cn0KCi8vIEZ1bmN0aW9uIHRvIGNoZWNrIGlmIGdpdmVuIG5vZGUgaXMgYSBsZWFmIG5vZGUgb3Igbm90CmJvb2wgaXNMZWFmKE5vZGUqIG5vZGUpCnsKICAgIHJldHVybiAobm9kZS0+bGVmdCA9PSBudWxscHRyICYmIG5vZGUtPnJpZ2h0ID09IG51bGxwdHIpOwp9CgovLyBSZWN1cnNpdmUgZnVuY3Rpb24gdG8gcHJpbnQgcm9vdC10by1sZWFmIHBhdGggZm9yIGEgZ2l2ZW4gbGVhZgp2b2lkIHByaW50UGF0aFJlY3Vyc2l2ZShOb2RlKiBjdXJyLCB1bm9yZGVyZWRfbWFwPE5vZGUqLCBOb2RlKj4gbWFwKQp7CiAgICAvLyBiYXNlIGNhc2UgOiBjdXJyIGlzIHJvb3Qgbm9kZSAocGFyZW50IG9mIHJvb3Qgbm9kZSBpcyBudWxsKQogICAgaWYgKGN1cnIgPT0gbnVsbHB0cikKICAgICAgICByZXR1cm47CgogICAgLy8gcmVjdXJzaXZlbHkgY2FsbCBwYXJlbnQgbm9kZQogICAgcHJpbnRQYXRoUmVjdXJzaXZlKG1hcFtjdXJyXSwgbWFwKTsKICAgIGNvdXQgPDwgY3Vyci0+ZGF0YSA8PCAoaXNMZWFmKGN1cnIpID8gIlxuIiA6ICIgLT4gIik7Cn0KCi8vIEl0ZXJhdGl2ZSBmdW5jdGlvbiB0byBwcmludCBsZWFmLXRvLXJvb3QgcGF0aCBmb3IgYSBnaXZlbiBsZWFmCi8vIEZvciBwcmludGluZyByb290LXRvLWxlYWYgcGF0aCwgd2UgY2FuIHVzZSBwcmludFBhdGhSZWN1cnNpdmUoKSBvciBhIHN0YWNrIAp2b2lkIHByaW50UGF0aEl0ZXJhdGl2ZShOb2RlKiBsZWFmTm9kZSwgdW5vcmRlcmVkX21hcDxOb2RlKiwgTm9kZSo+IG1hcCkKewogICAgLy8gc3RhcnQgZnJvbSB0aGUgbGVhZiBub2RlCiAgICBOb2RlKiBjdXJyID0gbGVhZk5vZGU7CgogICAgLy8gbG9vcCB0aWxsIHJvb3Qgbm9kZSBpcyByZWFjaGVkIGFuZCBwcmludCBlYWNoIG5vZGUgaW4gdGhlIHBhdGgKICAgIHdoaWxlIChtYXBbY3Vycl0gIT0gbnVsbHB0cikKICAgIHsKICAgICAgICBjb3V0IDw8IGN1cnItPmRhdGEgPDwgIiAtPiAiOwogICAgICAgIGN1cnIgPSBtYXBbY3Vycl07CiAgICB9CiAgICAKICAgIGNvdXQgPDwgY3Vyci0+ZGF0YSA8PCBlbmRsOwp9CgovLyBJdGVyYXRpdmUgZnVuY3Rpb24gdG8gcGVyZm9ybSBpbi1vcmRlciB0cmF2ZXJzYWwgb2YgdGhlIHRyZWUKdm9pZCBpbm9yZGVySXRlcmF0aXZlKE5vZGUgKnJvb3QpCnsKICAgIC8vIGNyZWF0ZSBhbiBlbXB0eSBzdGFjawogICAgc3RhY2s8Tm9kZSo+IHN0YWNrOwoKICAgIC8vIG1hcCAoY2hpbGQsIHBhcmVudCkKICAgIHVub3JkZXJlZF9tYXA8Tm9kZSosIE5vZGUqPiBtYXA7CiAgICAKICAgIC8vIHBhcmVudCBvZiByb290IG5vZGUgaXMgbnVsbAogICAgbWFwW3Jvb3RdID0gbnVsbHB0cjsKCiAgICAvLyBzdGFydCBmcm9tIHJvb3Qgbm9kZSAoc2V0IGN1cnJlbnQgbm9kZSB0byByb290IG5vZGUpCiAgICBOb2RlICpjdXJyID0gcm9vdDsKCiAgICAvLyBpZiBjdXJyZW50IG5vZGUgaXMgbnVsbCBhbmQgc3RhY2sgaXMgYWxzbyBlbXB0eSwgd2UncmUgZG9uZQogICAgd2hpbGUgKCFzdGFjay5lbXB0eSgpIHx8IGN1cnIgIT0gbnVsbHB0cikKICAgIHsKICAgICAgICAvLyBpZiBjdXJyZW50IG5vZGUgaXMgbm90IG51bGwsIHB1c2ggaXQgdG8gdGhlIHN0YWNrIChkZWZlciBpdCkKICAgICAgICAvLyBhbmQgbW92ZSB0byBpdHMgbGVmdCBjaGlsZAogICAgICAgIGlmIChjdXJyICE9IG51bGxwdHIpCiAgICAgICAgewogICAgICAgICAgICBzdGFjay5wdXNoKGN1cnIpOwogICAgICAgIAogICAgICAgICAgICAvLyBpbmNsdWRlIGN1cnJlbnQgbm9kZSBsZWZ0IGFuZCByaWdodCBjaGlsZCBpbiBhIG1hcAogICAgICAgICAgICBpZiAoY3Vyci0+bGVmdCkKICAgICAgICAgICAgICAgIG1hcFtjdXJyLT5sZWZ0XSA9IGN1cnI7CiAgICAgICAgCiAgICAgICAgICAgIGlmIChjdXJyLT5yaWdodCkKICAgICAgICAgICAgICAgIG1hcFtjdXJyLT5yaWdodF0gPSBjdXJyOwoKICAgICAgICAgICAgY3VyciA9IGN1cnItPmxlZnQ7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIC8vIGVsc2UgaWYgY3VycmVudCBub2RlIGlzIG51bGwsIHdlIHBvcCBhbiBlbGVtZW50IGZyb20gdGhlIHN0YWNrLAogICAgICAgICAgICAvLyBwcmludCBpdCBhbmQgZmluYWxseSBzZXQgY3VycmVudCBub2RlIHRvIGl0cyByaWdodCBjaGlsZAogICAgICAgICAgICBjdXJyID0gc3RhY2sudG9wKCk7CiAgICAgICAgICAgIHN0YWNrLnBvcCgpOwoKICAgICAgICAgICAgLy8gaWYgbGVhZiBub2RlIGlzIGZvdW5kLCBwcmludCB0aGUgcGF0aAogICAgICAgICAgICBpZiAoaXNMZWFmKGN1cnIpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvLyBwcmludCBsZWFmLXRvLXJvb3QgcGF0aCBmb3IgY3VycmVudCBsZWFmCiAgICAgICAgICAgICAgICBwcmludFBhdGhJdGVyYXRpdmUoY3VyciwgbWFwKTsKCiAgICAgICAgICAgICAgICAvLyBwcmludCByb290LXRvLWxlYWYgcGF0aCBmb3IgY3VycmVudCBsZWFmCiAgICAgICAgICAgICAgICAvLyBwcmludFBhdGhSZWN1cnNpdmUoY3VyciwgbWFwKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgY3VyciA9IGN1cnItPnJpZ2h0OwogICAgICAgIH0KICAgIH0KfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbigpCnsKICAgIC8qIENvbnN0cnVjdCBiZWxvdyB0cmVlCiAgICAgICAgICAgMQogICAgICAgICAvICAgXCAKICAgICAgICAvICAgICBcCiAgICAgICAvICAgICAgIFwKICAgICAgMiAgICAgICAgIDMKICAgICAvIFwgICAgICAgLyBcCiAgICAvICAgXCAgICAgLyAgIFwKICAgNCAgICAgNSAgIDYgICAgIDcKICAgICAgICAgICAgLyBcCiAgICAgICAgICAgLyAgIFwKICAgICAgICAgIDggICAgIDkKICAgICovCgogICAgdmVjdG9yPHBhaXI8c3RyaW5nLCBpbnQ+PiBrZXlzID0KICAgIHsKICAgICAgICB7IiIsIDF9LCB7IkwiLCAyfSwgeyJSIiwgM30sIHsiTEwiLCA0fSwgeyJMUiIsIDV9LCB7IlJMIiwgNn0sCiAgICAgICAgeyJSUiIsIDd9LCB7IlJMTCIsIDh9LCB7IlJMUiIsIDl9CiAgICB9OwoKICAgIE5vZGUqIHJvb3QgPSBudWxscHRyOwoKICAgIGZvciAoYXV0byBwYWlyOiBrZXlzKQogICAgICAgIGluc2VydChyb290LCBwYWlyLmZpcnN0LCBwYWlyLnNlY29uZCk7CgogICAgaW5vcmRlckl0ZXJhdGl2ZShyb290KTsKCiAgICByZXR1cm4gMDsKfQ==