# Binary Search Trees

## Overview#

Binary Search Tree (BST) is a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Example:

8
/ \
3 10
/ \
1 6

## Tree Operations#

### Basic Operations#

• Search: If less, go left. If more, go right. If equal, search hits.
• Insert: If less, go left. If more, go right. If null, insert new element.
• Get: Same as search, return value corresponding to the key. Else, return null if key not found.
• Put: Perform search. If key in tree, reset value. Else, add new node.
• Hibbard Deletion: To delete a node with key k, search for node t with key k
• Case 0: If `t` has 0 children, delete `t` by setting parent link to null
• Case 1: If `t` has 1 child, delete `t` by replacing parent link to `t's` child link.
• Case 2: If `t` has 2 children,
• Find successor x of `t`
• Delete minimum in `t's` right subtree
• Put x in `t's` spot

We insert new elements into a BST by comparing the values of the right and left nodes. We traverse until we find an empty spot (i.e. the child is `None`).

Similarly, for search, we keep comparing the search key to current node's value to determine whether to search on the right or left sub-tree.

### Ordered Operations#

• Min: Smallest key: Keep going left from root
• Max: Largest key: Keep going right from root
• Ceil: Smallest key >= given key
• Floor: Largest key <= given key
• Case 1: k equals key in node, where k is the given key
• Case 2: k is less than key in node: floor(k) is in left subtree
• Case 3: k is larger than key in node: floor(k) is in right subtree if there is any key <= k. Else, it is the key in the node.
• Rank: How many keys are < k?
• Select: Given a rank, what is the key which yields this rank?

## Time Complexity of Operations#

• Search: Average of `O(log n)`, Worst of `O(n)`
• Insert: Average of `O(log n)`, Worst of `O(n)`
• Delete: Average of `O(log n)`, Worst of `O(n)`

The worst case occurs when we have a linear BST. For example, if we insert a sorted or reverse sorted list of elements, we end up with a linear tree. In a way, this becomes like a linked list.

## Implementation#

### Tree Node#

class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None

### BST#

class BST(object):
def __init__(self, root):
self.root = Node(root)

### Insert Node#

def insert(self, val):
self.__insert(self.root, val)
def __insert(self, curr, val):
if(val < curr.data):
if curr.left:
self.__insert(curr.left, val)
else:
curr.left = Node(val)
else:
if curr.right:
self.__insert(curr.right, val)
else:
curr.right = Node(val)

### Search Tree#

def search(self, val):
return __search(self.root, val)
def __search(self, curr, val):
if curr is None:
return False
if(val == curr.data):
return True
elif val > curr.data:
return self.__search(curr.right, val)
else:
return self.__search(curr.left, val)

The above can also be implemented iteratively.