#include <iostream>
using namespace std;
class Node
{
public:
Node *left,
*right;
int value;
public:
Node(void) {
left = NULL;
right = NULL;
value = -1;
}
Node* getLeft() {return left;}
Node* getRight() {return right;}
int getValue() {return value;}
bool insert(Node** root, int val) {
if (!*root) {
*root = new Node();
(*root)->value = val;
(*root)->left = NULL; (*root)->right = NULL;
}
else {
if (val <= (*root)->value)
insert(&((*root)->left), val);
else
insert(&((*root)->right), val);
}
return true;
}
int inOrder(Node *root, int x) {
if (root && x > 0) {
x = inOrder(root->left, x);
if (x > 0) { cout << root->value << " "; x--; }
if (root->right && x > 0)
x = inOrder(root->right, x);
}
return x;
}
~Node(void);
};
int main() {
Node* root = NULL;
root->insert(&root, 100);
root->insert(&root, 50);
root->insert(&root, 150);
cout << "In-Order: ";
root->inOrder(root, 0);
cout << endl;
cout << "In-Order: ";
root->inOrder(root, 1);
cout << endl;
cout << "In-Order: ";
root->inOrder(root, 2);
cout << endl;
cout << "In-Order: ";
root->inOrder(root, 3);
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjbGFzcyBOb2RlCnsKcHVibGljOgogICAgTm9kZSAqbGVmdCwKCQkqcmlnaHQ7CglpbnQgdmFsdWU7CnB1YmxpYzoKCU5vZGUodm9pZCkgewoJbGVmdCA9IE5VTEw7CglyaWdodCA9IE5VTEw7Cgl2YWx1ZSA9IC0xOwoJfQoJTm9kZSogZ2V0TGVmdCgpIHtyZXR1cm4gbGVmdDt9CglOb2RlKiBnZXRSaWdodCgpIHtyZXR1cm4gcmlnaHQ7fQoJaW50IGdldFZhbHVlKCkge3JldHVybiB2YWx1ZTt9CgoJYm9vbCBpbnNlcnQoTm9kZSoqIHJvb3QsIGludCB2YWwpIHsKCWlmICghKnJvb3QpIHsKCQkqcm9vdCA9IG5ldyBOb2RlKCk7CgkJKCpyb290KS0+dmFsdWUgPSB2YWw7CgkJKCpyb290KS0+bGVmdCA9IE5VTEw7ICgqcm9vdCktPnJpZ2h0ID0gTlVMTDsKCX0KCWVsc2UgewoJCWlmICh2YWwgPD0gKCpyb290KS0+dmFsdWUpCgkJCWluc2VydCgmKCgqcm9vdCktPmxlZnQpLCB2YWwpOwoJCWVsc2UKCQkJaW5zZXJ0KCYoKCpyb290KS0+cmlnaHQpLCB2YWwpOwoJfQoJcmV0dXJuIHRydWU7CiAgICB9CgkKCWludCBpbk9yZGVyKE5vZGUgKnJvb3QsIGludCB4KSB7CglpZiAocm9vdCAmJiB4ID4gMCkgewoJCXggPSBpbk9yZGVyKHJvb3QtPmxlZnQsIHgpOwogICAgICAgIAoJCWlmICh4ID4gMCkgeyBjb3V0IDw8IHJvb3QtPnZhbHVlIDw8ICIgIjsgeC0tOyB9CiAgICAgICAgCgkJaWYgKHJvb3QtPnJpZ2h0ICYmIHggPiAwKQoJCXggPSBpbk9yZGVyKHJvb3QtPnJpZ2h0LCB4KTsKCX0KCXJldHVybiB4OwogICAgfQoJfk5vZGUodm9pZCk7Cn07CgppbnQgbWFpbigpIHsKCU5vZGUqIHJvb3QgPSBOVUxMOwoJcm9vdC0+aW5zZXJ0KCZyb290LCAxMDApOwoJcm9vdC0+aW5zZXJ0KCZyb290LCA1MCk7Cglyb290LT5pbnNlcnQoJnJvb3QsIDE1MCk7Cgljb3V0IDw8ICJJbi1PcmRlcjogIjsKCXJvb3QtPmluT3JkZXIocm9vdCwgMCk7Cgljb3V0IDw8IGVuZGw7CiAgICBjb3V0IDw8ICJJbi1PcmRlcjogIjsKICAgIHJvb3QtPmluT3JkZXIocm9vdCwgMSk7Cgljb3V0IDw8IGVuZGw7CiAgICBjb3V0IDw8ICJJbi1PcmRlcjogIjsKICAgIHJvb3QtPmluT3JkZXIocm9vdCwgMik7Cgljb3V0IDw8IGVuZGw7CiAgICBjb3V0IDw8ICJJbi1PcmRlcjogIjsKICAgIHJvb3QtPmluT3JkZXIocm9vdCwgMyk7Cgljb3V0IDw8IGVuZGw7CglyZXR1cm4gMDsKCX0=