# Data Structure (II) - 01 - 2 Binary Search Tree
> PART (II) - 01 - 2
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
> All the code in this part $\rightarrow$ [BST](https://github.com/Benny0w0Liu/Data-Structure-Learning/tree/main/Tree/BST)
>This part will be fucking long since it is really new concept. (also because almost half of the [video](https://www.youtube.com/watch?v=B31LgI4Y4DQ&t=20624s) is talking about this, and the video is over 9 hours long)
# Binary Search Tree
Binary Search Tree, also called BST, is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child.
* the left child containing values <= the parent node
* the right child containing values > the parent node.
This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
| | Array<br>(unsorted)| Link list | Array<br>(sorted) |BST |
| -------- | -------- | -------- |---|---|
|Search(x)| $O(n)$ | $O(n)$ | $O(log(n))$ |$O(log(n))$|
|Insert(x)| $O(1)$ | $O(1)$ | $O(n)$ |$O(log(n))$|
|Remove(x)| $O(n)$ | $O(n)$ | $O(n)$ |$O(log(n))$|
We acctually use this concept before, remember the quick sort and binary search?
# Implementation(C++)
First of all, please remember an important concept, tree and subtree, any node in the tree can be the root of subtree. I highly recimmend you to draw some tree to understand the codes below.
## initialize a tree
```cpp
int main(){
Node* root=NULL;
}
```
## insert
insert a node to the according root.
```cpp=
void insert(Node** rootPtr, int x){
Node* root = *rootPtr;
if(*rootPtr==NULL){//if empty
*rootPtr=new Node(x);
}else if(x<=root->data){//if x <= root, insert to left
insert(&(root->left), x);
}else{//if x > root, insert to right
insert(&(root->right), x);
}
}
```
```cpp
int main(){
Node* root=NULL;
insert(&root,10);
insert(&root,15);
insert(&root,20);
insert(&root,25);
insert(&root,8);
insert(&root,12);
insert(&root,2);
}
```
## search
check if the value is in the tree.
```cpp=
Node* search(Node* root, int x){
if(root==NULL){
return NULL;
}else if(root->data==x){
return root;
}else if(x<=root->data){
search(root->left, x);
}else{
search(root->right, x);
}
}
```
```cpp
int n=15;
if(search(root, n))cout<<search(root, n)->data<<" founded, at "<<search(root, n)<<endl;
else cout<<n<<" is not in the tree"<<endl;
```
## find min & max
* minimum will be the leftmost node of tree.
* maximum will be the rightmost node of tree.
The tree can break into two subtree, and the minimum number must be at the left, so just go to left node untill it doesn't have any child, vice versa.
```cpp=
Node* minimum(Node* root){
if(root==NULL){
cout<<"the tree is empty";
return NULL;
}
if(root->left==NULL)return root->left;
return minimum(root->left);
}
Node* maximum(Node* root){
if(root==NULL){
cout<<"the tree is empty";
return NULL;
}
if(root->right==NULL)return root->right;
return maximum(root->right);
}
```
## check if a binary tree is BST
According to the rule:
* root's left children <= root
* root's right children > root
We might met the situation's that it have 0, 1 or 2 children, therefore, we will come across with 3 situation
1. it is a null or it has 0 child $\rightarrow$ true
2. it has only 1 child $\rightarrow$ check if the other child follows the rules, and go to subtree
3. it has 2 child $\rightarrow$ check if both follow the rules, and go to both subtrees.
```cpp=
bool isBST(Node* root){
if(root==NULL || (root->left==NULL && root->right==NULL)) {
return true;
}else if(root->left!=NULL && root->right!=NULL){
return root->left->data <= root->data && root->right->data > root->data && isBST(root->left) && isBST(root->right);
}else if(root->left==NULL){
return root->right->data > root->data && isBST(root->right);
}else if(root->right==NULL){
return root->left->data <= root->data && isBST(root->left);
}
}
```
## delete
Similar to the last operation, there are 3 case in deletion. Assume we want to delete `x`.
1. `x` has 0 child
* just free it.
* 
2. `x` has 1 child
* connect the parents to the children, and free it(just like what we do in link list)
* 
3. `x` has 2 children
If it have 2 children we can choose left or right subtree to connect to the parents.
* choose left
* find the max value `m` in the subtree, replace `x` with `m`, and delete node m.
* choose right
* find the min value `m` in the subtree, replace `x` with `m`, and delete the node `m`.
* 
```cpp=
void deleteNode(Node** rootPtr, int x){
Node* root= *rootPtr;
if(*rootPtr==NULL)return;
if(x<root->data){
deleteNode(&(root->left), x);//visit left
}else if(x>root->data){
deleteNode(&(root->right), x);//visit right
}else{
if(root->right==NULL && root->left==NULL){//0 child
delete *rootPtr;
*rootPtr=NULL;
}else if(root->left==NULL){//1 child
Node* temp = *rootPtr;
*rootPtr = (*rootPtr)->right;
delete temp;
}else if(root->right==NULL){//1 child
Node* temp = *rootPtr;
*rootPtr = (*rootPtr)->left;
delete temp;
}else{//2 children
Node* min = minimum((*rootPtr)->right);
(*rootPtr)->data = min->data;
deleteNode(&(root->right),min->data);
}
}
}
```
## inorder successor
first of all, WTF is this?? Well it is actually pretty simple. Remember the inorder traversal?
It just means next number of given number in inorder traversal.
So how do we find it?
* Case 1: Node has right subtree.
* Go to the leftmost(min) node in right subtree.
* Case 2: No right subtree
* Go to the nearest ancestor for given node would be in left subtree.
```cpp=
Node* getInorderSuccessor(Node* root, int data){
Node* current = search(root, data);
if(current==NULL) return NULL;
if(current->right!=NULL){
return minimum(root->right);
}else{
Node* successor = NULL;
Node* ancestor = root;
while(current!=ancestor){
if(current->data<ancestor->data){
successor=ancestor;
ancestor=ancestor->left;
}else{
ancestor=ancestor->right;
}
}
return successor;
}
}
```
Sign in with Wallet
Connect another wallet