#include<bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;
Node(int x) {
val = x;
left = NULL;
right = NULL;
}
};
Node* insert(Node* root, int x) {
if (root == NULL) {
root = new Node(x);
} else if (x < root->val) {
root->left = insert(root->left, x);
} else {
root->right = insert(root->right, x);
}
return root;
}
void preorder(Node* root) {
if(root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(Node* root) {
if(root == NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(Node* root) {
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
bool find(Node* root, int val) {
if (root == NULL) {
return 0; // Value not found
}
if (root->val == val) {
return 1; // Value found
} else if (val < root->val) {
return find(root->left, val);
} else {
return find(root->right, val);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
Node* root = NULL;
// Insert elements into BST
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 6);
root = insert(root, 8);
// Print elements of BST in sorted order
cout << "Inorder traversal of BST: ";
inorder(root);
cout << "\n";
// Find elements in BST
cout << "Find 3 in BST: " << find(root, 3) << endl; // Output should be 1
cout << "Find 9 in BST: " << find(root, 9) << endl; // Output should be 0
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBOb2RlIHsKICAgIGludCB2YWw7CiAgICBOb2RlKiBsZWZ0OwogICAgTm9kZSogcmlnaHQ7CgogICAgTm9kZShpbnQgeCkgewogICAgICAgIHZhbCA9IHg7CiAgICAgICAgbGVmdCA9IE5VTEw7CiAgICAgICAgcmlnaHQgPSBOVUxMOwogICAgfQp9OwoKTm9kZSogaW5zZXJ0KE5vZGUqIHJvb3QsIGludCB4KSB7CiAgICBpZiAocm9vdCA9PSBOVUxMKSB7CiAgICAgICAgcm9vdCA9IG5ldyBOb2RlKHgpOwogICAgfSBlbHNlIGlmICh4IDwgcm9vdC0+dmFsKSB7CiAgICAgICAgcm9vdC0+bGVmdCA9IGluc2VydChyb290LT5sZWZ0LCB4KTsKICAgIH0gZWxzZSB7CiAgICAgICAgcm9vdC0+cmlnaHQgPSBpbnNlcnQocm9vdC0+cmlnaHQsIHgpOwogICAgfQogICAgcmV0dXJuIHJvb3Q7Cn0KCnZvaWQgcHJlb3JkZXIoTm9kZSogcm9vdCkgewogICAgaWYocm9vdCA9PSBOVUxMKSByZXR1cm47CgogICAgY291dCA8PCByb290LT52YWwgPDwgIiAiOwogICAgcHJlb3JkZXIocm9vdC0+bGVmdCk7CiAgICBwcmVvcmRlcihyb290LT5yaWdodCk7Cn0KCnZvaWQgaW5vcmRlcihOb2RlKiByb290KSB7CiAgICBpZihyb290ID09IE5VTEwpIHJldHVybjsKCiAgICBpbm9yZGVyKHJvb3QtPmxlZnQpOwogICAgY291dCA8PCByb290LT52YWwgPDwgIiAiOwogICAgaW5vcmRlcihyb290LT5yaWdodCk7Cn0KCnZvaWQgcG9zdG9yZGVyKE5vZGUqIHJvb3QpIHsKICAgIGlmKHJvb3QgPT0gTlVMTCkgcmV0dXJuOwoKICAgIHBvc3RvcmRlcihyb290LT5sZWZ0KTsKICAgIHBvc3RvcmRlcihyb290LT5yaWdodCk7CiAgICBjb3V0IDw8IHJvb3QtPnZhbCA8PCAiICI7Cn0KCmJvb2wgZmluZChOb2RlKiByb290LCBpbnQgdmFsKSB7CiAgICBpZiAocm9vdCA9PSBOVUxMKSB7CiAgICAgICAgcmV0dXJuIDA7IC8vIFZhbHVlIG5vdCBmb3VuZAogICAgfQogICAgaWYgKHJvb3QtPnZhbCA9PSB2YWwpIHsKICAgICAgICByZXR1cm4gMTsgLy8gVmFsdWUgZm91bmQKICAgIH0gZWxzZSBpZiAodmFsIDwgcm9vdC0+dmFsKSB7CiAgICAgICAgcmV0dXJuIGZpbmQocm9vdC0+bGVmdCwgdmFsKTsKICAgIH0gZWxzZSB7CiAgICAgICAgcmV0dXJuIGZpbmQocm9vdC0+cmlnaHQsIHZhbCk7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgY2luLnRpZSgwKTsKICAgIE5vZGUqIHJvb3QgPSBOVUxMOwoKICAgIC8vIEluc2VydCBlbGVtZW50cyBpbnRvIEJTVAogICAgcm9vdCA9IGluc2VydChyb290LCA1KTsKICAgIHJvb3QgPSBpbnNlcnQocm9vdCwgMyk7CiAgICByb290ID0gaW5zZXJ0KHJvb3QsIDcpOwogICAgcm9vdCA9IGluc2VydChyb290LCAyKTsKICAgIHJvb3QgPSBpbnNlcnQocm9vdCwgNCk7CiAgICByb290ID0gaW5zZXJ0KHJvb3QsIDYpOwogICAgcm9vdCA9IGluc2VydChyb290LCA4KTsKCiAgICAvLyBQcmludCBlbGVtZW50cyBvZiBCU1QgaW4gc29ydGVkIG9yZGVyCiAgICBjb3V0IDw8ICJJbm9yZGVyIHRyYXZlcnNhbCBvZiBCU1Q6ICI7CiAgICBpbm9yZGVyKHJvb3QpOwogICAgY291dCA8PCAiXG4iOwoKICAgIC8vIEZpbmQgZWxlbWVudHMgaW4gQlNUCiAgICBjb3V0IDw8ICJGaW5kIDMgaW4gQlNUOiAiIDw8IGZpbmQocm9vdCwgMykgPDwgZW5kbDsgLy8gT3V0cHV0IHNob3VsZCBiZSAxCiAgICBjb3V0IDw8ICJGaW5kIDkgaW4gQlNUOiAiIDw8IGZpbmQocm9vdCwgOSkgPDwgZW5kbDsgLy8gT3V0cHV0IHNob3VsZCBiZSAwCgogICAgcmV0dXJuIDA7Cn0K