# What is Binary Search Tree (BST) ?

Binary Search Tree or BST, is a Binary tree based data sctructure, that keeps all of its elements in sorted order. We also call it, **ordered** or **sorted binary trees**.

It was invented by P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard in 1960.

**Specifications**

- Faster lookup for elements
- Faster insertion of new elements
- and faster removal of elements from tree
- Left subtree of a node contains only nodes with keys lesser than the node’s key.
- Right subtree of a node contains only nodes with keys greater than the node’s key.
- Left and right subtree each must also be a binary search tree.

So, overall, BST is a container that keeps elements inside it and provides access to it in efficient manner.

**Complexity**

Operation | Average Case |
Worst case |
---|---|---|

Space | O(n) |
O(n) |

Search | O(log n) |
O(n) |

Insert | O(log n) |
O(n) |

Delete | O(log n) |
O(n) |

**How does it work ?**

BST keeps all of its elemets in sorted order hence operations like, search, insert and delete works based Binary search and this gives it advantage.