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: n2 (descending/ascending order)
3. Average Case (interesting) : nlogn