# 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

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.