Binary Search Tree

Binary search tree is a ordered dictionary in which keys for each node in the tree has total order. It is also called ordered or sorted binary tree.

We can find, insert, remove entries relatively fast. Quickly find node with minumum or maximum keys or keas near another key.

We can find words with close spelling without knowing exact spelling or can find something like smallest number that is greater than 100.

BST is used as data structures for sets, multisets, associated arrays etc.

Binary search tree time complexity

	Average	Worst case
Search	O(lg n)	O(n)
Insert	O(lg n)	O(n)
Delete	O(lg n)	O(n)

Binary Search Tree Invariant

For any node X, the tree the left subtree of X contains nodes with keys less than X's key and right subtree contains nodes with greater than X's key nad both subtree must be binary search trees themselves.

Any node may have data attached to it.

We can get all the keys in sorted order by doing inorder traversal of the tree.

Operations

Find a node with key K

Start from the root as current node
Untill the key is found or no more node to visit
    If the current node's key is equal to K return the current node
    If current node's key is smaller than K select right node as current node
    If current node's key is greater than K select left node as current node
Return NULL

Find smallest key >=K and largest key <=K

While searching for a key K we encounter both of these keys if K is not in the tree. We need to keep track of the keys. When we go right node we have key smaller than K. When we go left we have key greater than K. Last of these two is the smallest key >=K and largest key <=K.

Find a node with smallest key

Starting form root continously select left child as long as possible. Last node will be the node with smallest key of the tree.

Find a node with largest key

Starting form root continously select right child as long as possible. Last node will be the node with largest key of the tree.

Insert a node

Let K be the key we want to insert.
Search the tree for key K untill it is found or we hit NULL node
    If NULL replace the NULL node with  K.
    If K is found insert new node as left or right node with key K

Delete a node

Let K be the key of the node we want to delete.
Search for the node X with Key K.
    (a)If not found return.
    (b)If found and node has no child detach the key from its parent.
    (c)If found and node has one child replace the node with its child node.
    (d)If found and node has two children-
            Find the node Y with smallest key in the RIGHT subtree of the node to delete
                Y do not have any left subtree so it can be removed easily using (a)  or (b)
                Replace X with Y