What are advantages and disadvantages of BST?

Advantages of BST:

• If we implement a balanced binary search tree, we can always keep the cost of insert(), delete(), lookup() to O(log n)
• BST is much faster than an array at search, insert, and delete (O(log n) vs O(n))
• Code is simple relative to other data structures

Disadvantages of BST:

• BST is slightly slower than an array at access (O(log n) vs O(1))
• A binary search tree can get out of balance (imbalanced) or become degenerated
• We should always implement a balanced binary search tree (using some self-balancing mechanism) – AVL tree, Red-Black tree, Splay tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.