# Binary Search Trees

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. When inserting or searching for an element in a binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.

Wikipedia

### Important Definitions

Binary Tree: A tree that starts at a single root and branches down, all nodes have a minimum of 0 children (leaves) and a maximum of 2 children.
Complete Binary Tree: All levels are full except at the bottom level, all levels are filled left to right.
Full Binary Tree: All nodes have 2 children or 0 children (leaf).
Binary Search Tree: A binary tree with the Search Tree Property.
Search Tree Property: For any node x, all nodes in it’s left subtree are less than x and all nodes in its right subtree are greater than or equal to x.

### Binary Search Tree Algorithms

```def search(key, node):
if node is None or node.key == key:
return node
if key < node.key:
return search(key, node.left)
else:
return search(key, node.right)```
```def insertion:
- Search and insert where we fell off tree```
```def find_min(node):
if node.left is None:
return node
else:
return find_min(node.left)```
```def find_max(node):
if node.right is None:
return node
else:
return find_max(node. right)```
```def successor(node):
if node.right:
return find_min(node.right)
else:
Go up until you find a node with it's parent on the right, return parent
```
```def delete(node):
if node is leaf:
delete node
if node has one child:
connect node parent to node child
delete node
if node has 2 children:
swap node with successor(node)
delete (node)
```

Runtime Complexity
Search: O(h)
Insert: O(h)
Find Min: O(h)
Find Max: O(h)
Successor: O(h)
Delete: O(h)
h can range from
O( log (n) ) – Best Case, Balanced BST
O(n) – Worst Case, Linked List BST