#include <iostream>
using namespace std;
bool found = false;
class BST
{
public:
long long data, index;
BST *left, *right;
// Default constructor.
BST();
// Parameterized constructor.
BST(long long, long long);
// Insert function.
BST* Insert(BST*, long long, long long);
// Inorder traversal.
void IndexSearch(BST*);//, long long);
};
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
, index(1)
{
}
BST ::BST(long long value, long long i)
{
data = value;
left = right = NULL;
index = i;
}
BST* BST ::Insert(BST* root, long long index, long long value)
{
if (!root)
{
return new BST(value, index);
}
if (value > root->data)
{
root->index += 1;
root->right = Insert(root->right, index, value);
}
else
{
root->left = Insert(root->left, index + 1, value);
}
return root;
}
// Inorder traversal function.
// This gives data in sorted order.
void BST ::IndexSearch(BST* root)//, long long data)
{
if (!root || found) {
return;
}
IndexSearch(root->right);//, data);
cout << "index: " << root->index;
cout << " data: " << root->data << endl;
IndexSearch(root->left);//, data);
}
// Driver code
int main()
{
long long n, type, data;
BST b, *root = NULL;
cin >> n;
while (n--) {
cin >> type;
cin >> data;
if (!root) {
if (type == 1) root = b.Insert(root, 1, data);
else if (type == 2) cout << "Data tidak ada\n";
}
else {
if (type == 1) {
b.Insert(root, root->index, data);
}
/*else {
b.IndexSearch(root, data);
if (!found) cout << "Data tidak ada\n";
}*/
}
found = false;
}
b.IndexSearch(root);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKYm9vbCBmb3VuZCA9IGZhbHNlOwogCmNsYXNzIEJTVAp7CnB1YmxpYzogCiAgICBsb25nIGxvbmcgZGF0YSwgaW5kZXg7CiAgICBCU1QgKmxlZnQsICpyaWdodDsKIAogICAgLy8gRGVmYXVsdCBjb25zdHJ1Y3Rvci4KICAgIEJTVCgpOwogICAgCiAgICAvLyBQYXJhbWV0ZXJpemVkIGNvbnN0cnVjdG9yLgogICAgQlNUKGxvbmcgbG9uZywgbG9uZyBsb25nKTsKIAogICAgLy8gSW5zZXJ0IGZ1bmN0aW9uLgogICAgQlNUKiBJbnNlcnQoQlNUKiwgbG9uZyBsb25nLCBsb25nIGxvbmcpOwogCiAgICAvLyBJbm9yZGVyIHRyYXZlcnNhbC4KICAgIHZvaWQgSW5kZXhTZWFyY2goQlNUKik7Ly8sIGxvbmcgbG9uZyk7Cn07CiAKCkJTVCA6OkJTVCgpCiAgICA6IGRhdGEoMCkKICAgICwgbGVmdChOVUxMKQogICAgLCByaWdodChOVUxMKQogICAgLCBpbmRleCgxKQp7Cn0KIApCU1QgOjpCU1QobG9uZyBsb25nIHZhbHVlLCBsb25nIGxvbmcgaSkKewogICAgZGF0YSA9IHZhbHVlOwogICAgbGVmdCA9IHJpZ2h0ID0gTlVMTDsKICAgIGluZGV4ID0gaTsKfQogCgpCU1QqIEJTVCA6Okluc2VydChCU1QqIHJvb3QsIGxvbmcgbG9uZyBpbmRleCwgbG9uZyBsb25nIHZhbHVlKQp7CiAgICBpZiAoIXJvb3QpCiAgICB7CiAgICAgICAgcmV0dXJuIG5ldyBCU1QodmFsdWUsIGluZGV4KTsKICAgIH0KIAogICAgaWYgKHZhbHVlID4gcm9vdC0+ZGF0YSkKICAgIHsKICAgIAlyb290LT5pbmRleCArPSAxOwogICAgICAgIHJvb3QtPnJpZ2h0ID0gSW5zZXJ0KHJvb3QtPnJpZ2h0LCBpbmRleCwgdmFsdWUpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHJvb3QtPmxlZnQgPSBJbnNlcnQocm9vdC0+bGVmdCwgaW5kZXggKyAxLCB2YWx1ZSk7CiAgICB9CiAgICAKICAgIHJldHVybiByb290Owp9CiAKLy8gSW5vcmRlciB0cmF2ZXJzYWwgZnVuY3Rpb24uCi8vIFRoaXMgZ2l2ZXMgZGF0YSBpbiBzb3J0ZWQgb3JkZXIuCnZvaWQgQlNUIDo6SW5kZXhTZWFyY2goQlNUKiByb290KS8vLCBsb25nIGxvbmcgZGF0YSkKewogICAgaWYgKCFyb290IHx8IGZvdW5kKSB7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgSW5kZXhTZWFyY2gocm9vdC0+cmlnaHQpOy8vLCBkYXRhKTsKICAgIGNvdXQgPDwgImluZGV4OiAiIDw8IHJvb3QtPmluZGV4OwogICAgY291dCA8PCAiIGRhdGE6ICIgPDwgcm9vdC0+ZGF0YSA8PCBlbmRsOwogICAgSW5kZXhTZWFyY2gocm9vdC0+bGVmdCk7Ly8sIGRhdGEpOwp9CiAKLy8gRHJpdmVyIGNvZGUKaW50IG1haW4oKQp7Cglsb25nIGxvbmcgbiwgdHlwZSwgZGF0YTsKICAgIEJTVCBiLCAqcm9vdCA9IE5VTEw7CiAgICAKICAgIGNpbiA+PiBuOwogICAgCiAgICB3aGlsZSAobi0tKSB7CiAgICAJY2luID4+IHR5cGU7CiAgICAJY2luID4+IGRhdGE7CiAgICAJaWYgKCFyb290KSB7CiAgICAJCWlmICh0eXBlID09IDEpCQlyb290ID0gYi5JbnNlcnQocm9vdCwgMSwgZGF0YSk7CiAgICAJCWVsc2UgaWYgKHR5cGUgPT0gMikJY291dCA8PCAiRGF0YSB0aWRhayBhZGFcbiI7CiAgICAJfQogICAgCWVsc2UgewogICAgCQlpZiAodHlwZSA9PSAxKSB7CiAgICAJCQliLkluc2VydChyb290LCByb290LT5pbmRleCwgZGF0YSk7CiAgICAJCX0KICAgIAkJLyplbHNlIHsJCiAgICAJCQliLkluZGV4U2VhcmNoKHJvb3QsIGRhdGEpOwoJCQkJaWYgKCFmb3VuZCkgY291dCA8PCAiRGF0YSB0aWRhayBhZGFcbiI7CQkgICAgCQogICAgCQl9Ki8KICAgIAl9CiAgICAJZm91bmQgPSBmYWxzZTsKICAgIH0KICAgIGIuSW5kZXhTZWFyY2gocm9vdCk7CglyZXR1cm4gMDsKfQ==