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.
