Note: use the github provided TOC for navigaing.
node* build(){ // read a list of number till -1 and also these numbers will be inserted into BST int d; cinĀ»d; node* root==NULL; while(d!=-1){ root = insert_in_bst(root,d); cinĀ»d; } return root; }
### BST searching:
- BST is very effecient in searching.
- complexity if O(H), in average case, in max case its O(N) in min case its O(logN).
```cpp
bool search(node*root,key){
if(root==NULL){
return false;
}
if(key==root->data){
return true;
}
// recursive case
if(key<=root->data){
return search(root->left,key);
}
else{
return search(root->right,key);
}
}
it has mainly three case,
node* delet_bst(node* root, int data){
if(root==NULL){
return NULL;
}
else if(data<root->data){
root->left = delet_bst(root->left,data);
return root;
}
else if(data==root->data){
// found the node to delete 3 cases
// 1st. Node has 0 children
if(root->left==NULL && root->right==NULL){
node* temp = root->left;
delete root;
return NULL;
}
//2. node has 2 children
if(root->left!=NULL && root->right==NULL){
node*temp = root->left;
delete root;
return temp;
}
if(root->left==NULL && root->right!=NULL){
node*temp = root->right;
delete root;
return temp;
}
//3. node has 2 children
node *replace = root->right;
// find the inorder successar from the right subtree
while(replace->left!=NULL){
replace = replace->left;
}
root->data = replace->daata;
root->right = delet_bst(root->right,replace->data);
return root;
}
else{
root->right = delet_bst(root->right,data);
return root;
}
}