//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;
}
Ly9CU1QgQmluYXJ5IHNlYXJjaCB0cmVlIGRlbW8KLy9QZXRyIEJ1YmVuIDEyLDMuMjAyNQoKI2luY2x1ZGUgPGlvc3RyZWFtPgovKioqKioqKioqCnNlYXJjaChyb290KQppZiByb290PT1udWxscHRyCglyZXR1cm4gbnVsbHB0cgppZiBudW1iZXI9PXJvb3QuZGF0YQoJcmV0dXJuIHJvb3QuZGF0YQppZiBudW1iZXI8cm9vdC5kYXRhCglyZXR1cm4gc2VhcmNoKHJvb3QtPmxlZnQpCmlmIG51bWJlcj5yb290LmRhdGEKCXJldHVybiBzZWFyY2gocm9vdC0+cmlnaHQpCgppbnNlcnQKaWYgbm9kZT09bnVsbHB0cgoJY3JlYXRlbm9kZShudW1iZXIpCmlmIG51bWJlciA8IG5vZGUtPmRhdGEKCW5vZGUtPmxlZnQ9IGluc2VydChub2RlLT5sZWZ0LG51bWJlcikKZWxzZQpub2RlLT5yaWdodD0gaW5zZXJ0KG5vZGUtPnJpZ2h0LG51bWJlcikKcmV0dXJuIG5vZGUKKioqKioqKioqLwoKc3RydWN0IG5vZGV7CglpbnQga2V5OwoJbm9kZSogbGVmdCwqcmlnaHQ7Cn07CgovLyBDcmVhdGUgYSBub2RlCnN0cnVjdCBub2RlICpuZXdOb2RlKGludCBpdGVtKSB7Ci8vCXN0cnVjdCBub2RlKnQgeyhzdHJ1Y3Qgbm9kZSopbWFsbG9jKHNpemVvZihub2RlKSl9OwogIHN0cnVjdCBub2RlICp0ZW1wID0gbmV3IG5vZGUoKTsKICB0ZW1wLT5rZXkgPSBpdGVtOwogIHRlbXAtPmxlZnQgPSB0ZW1wLT5yaWdodCA9IE5VTEw7CiAgcmV0dXJuIHRlbXA7Cn0KCm5vZGUgKmluc2VydChub2RlKiBub2RlLCBpbnQga2V5KXsKCWlmKG5vZGU9PW51bGxwdHIpCgkJcmV0dXJuIG5ld05vZGUoa2V5KTsKCWlmKGtleTxub2RlLT5rZXkpCgkJbm9kZS0+bGVmdCA9aW5zZXJ0KG5vZGUtPmxlZnQsa2V5KTsKCWVsc2UKCQlub2RlLT5yaWdodD1pbnNlcnQobm9kZS0+cmlnaHQsa2V5KTsKCQkKCXJldHVybiBub2RlOwp9Cgpub2RlKiBzZWFyY2gobm9kZSogbiwgaW50IGtleSl7CglpZihuPT1udWxscHRyKQoJCXJldHVybiBudWxscHRyOwoJaWYobi0+a2V5PT1rZXkpCgkJcmV0dXJuIG47CglpZihrZXk8bi0+a2V5KXsKCQlyZXR1cm4gc2VhcmNoKG4tPmxlZnQsa2V5KTt9CgllbHNlIGlmIChrZXk+bi0+a2V5KXsKCQlyZXR1cm4gc2VhcmNoKG4tPnJpZ2h0LGtleSk7fQkKfQoJCnZvaWQgaW5vcmRlcihub2RlKiBuKXsKCWlmKG4hPW51bGxwdHIpewoJCWlub3JkZXIobi0+bGVmdCk7CgkJc3RkOjpjb3V0PDxuLT5rZXk8PCIgIjsKCQlpbm9yZGVyKG4tPnJpZ2h0KTsKCX0KfQoKaW50IG1haW4oKSB7CglzdHJ1Y3Qgbm9kZSogcm9vdHsgbmV3Tm9kZSgxKX07CglpbnNlcnQocm9vdCwyKTsKCQoJc3RkOjpjb3V0PDxzZWFyY2gocm9vdCwxKS0+a2V5PDxzdGQ6OmVuZGw7CglzdGQ6OmNvdXQ8PCJpbiBvcmRlcjoiPDxzdGQ6OmVuZGw7Cglpbm9yZGVyKHJvb3QpOwoKCXJldHVybiAwOwp9