//BST Binary search tree demo
//Petr Buben 12,3.2025
#include <iostream>
/*
search(root)
if root==nullptr
return nullptr
if number==root.data
return root.data
if number<root.data
return search(root->left)
if number>root.data
return search(root->right)
insert
if node==nullptr
createnode(number)
if number < node->data
node->left= insert(node->left,number)
else
node->right= insert(node->right,number)
return node
*/
struct node{
int key;
node* left,*right;
};
// Create a node
struct node *newNode(int item) {
// struct node*t {(struct node*)malloc(sizeof(node))};
struct node *temp = new node();
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
node *insert(node* node, int key){
if(node==nullptr)
return newNode(key);
if(key<node->key)
node->left =insert(node->left,key);
else
node->right=insert(node->right,key);
return node;
}
node* search(node* n, int key){
if(n==nullptr)
return nullptr;
if(n->key==key)
return n;
if(key<n->key){
return search(n->left,key);}
else if (key>n->key){
return search(n->right,key);}
}
void inorder(node* n){
if(n!=nullptr){
inorder(n->left);
std::cout<<n->key<<" ";
inorder(n->right);
}
}
int main() {
struct node* root{ newNode(1)};
insert(root,2);
std::cout<<search(root,1)->key<<std::endl;
std::cout<<"in order:"<<std::endl;
inorder(root);
return 0;
}
Ly9CU1QgQmluYXJ5IHNlYXJjaCB0cmVlIGRlbW8KLy9QZXRyIEJ1YmVuIDEyLDMuMjAyNQoKI2luY2x1ZGUgPGlvc3RyZWFtPgovKgpzZWFyY2gocm9vdCkKaWYgcm9vdD09bnVsbHB0cgoJcmV0dXJuIG51bGxwdHIKaWYgbnVtYmVyPT1yb290LmRhdGEKCXJldHVybiByb290LmRhdGEKaWYgbnVtYmVyPHJvb3QuZGF0YQoJcmV0dXJuIHNlYXJjaChyb290LT5sZWZ0KQppZiBudW1iZXI+cm9vdC5kYXRhCglyZXR1cm4gc2VhcmNoKHJvb3QtPnJpZ2h0KQoKaW5zZXJ0CmlmIG5vZGU9PW51bGxwdHIKCWNyZWF0ZW5vZGUobnVtYmVyKQppZiBudW1iZXIgPCBub2RlLT5kYXRhCglub2RlLT5sZWZ0PSBpbnNlcnQobm9kZS0+bGVmdCxudW1iZXIpCmVsc2UKbm9kZS0+cmlnaHQ9IGluc2VydChub2RlLT5yaWdodCxudW1iZXIpCnJldHVybiBub2RlCiovCgpzdHJ1Y3Qgbm9kZXsKCWludCBrZXk7Cglub2RlKiBsZWZ0LCpyaWdodDsKfTsKCi8vIENyZWF0ZSBhIG5vZGUKc3RydWN0IG5vZGUgKm5ld05vZGUoaW50IGl0ZW0pIHsKLy8Jc3RydWN0IG5vZGUqdCB7KHN0cnVjdCBub2RlKiltYWxsb2Moc2l6ZW9mKG5vZGUpKX07CiAgc3RydWN0IG5vZGUgKnRlbXAgPSBuZXcgbm9kZSgpOwogIHRlbXAtPmtleSA9IGl0ZW07CiAgdGVtcC0+bGVmdCA9IHRlbXAtPnJpZ2h0ID0gTlVMTDsKICByZXR1cm4gdGVtcDsKfQoKbm9kZSAqaW5zZXJ0KG5vZGUqIG5vZGUsIGludCBrZXkpewoJaWYobm9kZT09bnVsbHB0cikKCQlyZXR1cm4gbmV3Tm9kZShrZXkpOwoJaWYoa2V5PG5vZGUtPmtleSkKCQlub2RlLT5sZWZ0ID1pbnNlcnQobm9kZS0+bGVmdCxrZXkpOwoJZWxzZQoJCW5vZGUtPnJpZ2h0PWluc2VydChub2RlLT5yaWdodCxrZXkpOwoJCQoJcmV0dXJuIG5vZGU7Cn0KCm5vZGUqIHNlYXJjaChub2RlKiBuLCBpbnQga2V5KXsKCWlmKG49PW51bGxwdHIpCgkJcmV0dXJuIG51bGxwdHI7CglpZihuLT5rZXk9PWtleSkKCQlyZXR1cm4gbjsKCWlmKGtleTxuLT5rZXkpewoJCXJldHVybiBzZWFyY2gobi0+bGVmdCxrZXkpO30KCWVsc2UgaWYgKGtleT5uLT5rZXkpewoJCXJldHVybiBzZWFyY2gobi0+cmlnaHQsa2V5KTt9CQp9CgkKdm9pZCBpbm9yZGVyKG5vZGUqIG4pewoJaWYobiE9bnVsbHB0cil7CgkJaW5vcmRlcihuLT5sZWZ0KTsKCQlzdGQ6OmNvdXQ8PG4tPmtleTw8IiAiOwoJCWlub3JkZXIobi0+cmlnaHQpOwoJfQp9CgppbnQgbWFpbigpIHsKCXN0cnVjdCBub2RlKiByb290eyBuZXdOb2RlKDEpfTsKCWluc2VydChyb290LDIpOwoJCglzdGQ6OmNvdXQ8PHNlYXJjaChyb290LDEpLT5rZXk8PHN0ZDo6ZW5kbDsKCXN0ZDo6Y291dDw8ImluIG9yZGVyOiI8PHN0ZDo6ZW5kbDsKCWlub3JkZXIocm9vdCk7CgoJcmV0dXJuIDA7Cn0=