Binary Search Tree

Features

• All the keys in left sub-tree are smaller than the ye value in root
• All the keys in right sub-tree are larger than the ye value in root
• Average depth is $O(\log n)$
• Maximum depth is $O(n)$

Deletion

1. Delete leaf node
2. Delete node with 1 sub-tree
3. Delete node with 2 sub-tree
   1. Replace node with smallest node of right sub-tree, OR
   2. Replace node with largest node of left sub-tree