Binary Search Tree

Binary Search Tree:

Also called Order/Sorted Binary Tree. BST is Binary tree with the property :

1. Left node(and hence sub-tree) contains only nodes with less key.

2. Right node contains only nodes with greater key value.

Most functions on BST are of order H where H is the height of the binary tree. Note that height could vary from n to logn deepening on if the tree is Full Binary tree or not.

Interesting Point: For Sorting the complexity is:

1. Best Case: nlogn

2. Worst Case: n² (descending/ascending order)

3. Average Case (interesting) : nlogn