Binary Tree

# 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:
• Search: Binary Search Tree:
• Insertion: Binary Search Tree:

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

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.

1. Find replacement node, and link replacement nodeâ€™s parent to replacement nodeâ€™s child (only should have one)
1. In our case, we will decide the replacement node as the max down the left subtree of the target node.
2. Insert replacement node in place of target node by updating the pointers
3. update the pointer of parent of target node to the replacement node
4. Delete target node

The image below is a little confusing

#### Option 3 (SLOW)

Copy over, and then delete a single node.

Learned in CS247.