---
# System prepended metadata

title: Data Structure (II) - 01 - 2 Binary Search Tree
tags: [Data Structure]

---

# 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.

![image](https://hackmd.io/_uploads/H1EJzdeoA.png)

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. 
    * ![image](https://hackmd.io/_uploads/SkgpMlXiC.png)

2. `x` has 1 child
    * connect the parents to the children, and free it(just like what we do in link list)
    * ![image](https://hackmd.io/_uploads/rJzRzg7jC.png)

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`.
    * ![image](https://hackmd.io/_uploads/BkpCb-7oR.png)
```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? 
![image](https://hackmd.io/_uploads/B18VwW7o0.png)
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;
    }
}
```