# Binary Search Tree (BST)

It is a special kind of Binary Tree that uses comparable keys to assign which direction a child is.

- Left child key < parent node key
- Right child key > parent node key
- There can be no duplicate node

BST invariant: for ALL subtrees, max(left subtree) < root < min(right subtree)

### Time Complexity

Assuming the tree is pretty balanced.

- Indexing: Binary Search Tree: $O(gn)$
- Search: Binary Search Tree: $O(gn)$
- Insertion: Binary Search Tree: $O(gn)$

### Implementation

Some of the functions with a BST are a little hard to grasp for me, because I need to use recursion.

Inserting and searching is fairly easy. You always insert at the end of the tree, not in the middle of tree.

###### Checking WellFormedness CS138 Final

We need to recursively check four things:

- this->left->key < this->key
- this->right->key > this->key
- this->maxLeft()->key < this->key
- this->minRight()->key > this->key

```
bool BST_Node::isWellformed() const {
// TODO - This is for you to implement. BST::isWellformedBST has been provided for you.
if (nullptr != this->left) {
assert(this->left->key < this->key);
assert(this->maxLeft()->key < this->key);
//Recursively check the left node
this->left->isWellformed();
}
if (nullptr != this->right) {
assert(this->right->key > this->key);
assert(this->minRight()->key > this->key);
// Recursively check the right node
this->right->isWellformed();
}
return true; //No assertions tripped, return true
}
```

Ahh, so I've already done this before.

There is this LeetCode question, which I haven’t done yet. https://leetcode.com/problems/validate-binary-search-tree/submissions/

## BST Deletion

#### Option 1 (BAD)

Add a boolean “zombie” flag to each node

- Zombie nodes are not printed
- Advantage is that it’s simple, but disadvantage long term performance degrades as tree is full of zombies

#### Option 2 (TO USE)

You handle three cases with the target node to delete.
**Case 1**: If the target node has no children, just delete it
**Case 2**: If the target node has a single children, link target node’s parent to target node’s children, and delete the target node
**Case 3**: Either with the max of the left subtree, or the min of the right subtree (guaranteed to only have 0 or 1 child, not 2 children by definition)

##### Example with Case 3

Circled in red is the target node. Circled in blue is the replacement node.

- Find replacement node, and link replacement node’s parent to replacement node’s child (only should have one)
- In our case, we will decide the replacement node as the max down the left subtree of the target node.

- Insert replacement node in place of target node by updating the pointers
- update the pointer of parent of target node to the replacement node
- Delete target node

The image below is a little confusing

#### Option 3 (SLOW)

Copy over, and then delete a single node.

## BST Range Search

Learned in CS247.