Binary Search Trees or BST is an ordered binary tree where all the nodes on the left of a node are less or equal to the node’s own value and all the values on the right are greater or equal to the node’s own value.
A Binary Tree is a tree with only two children, left and right.
Advantages of BST
- lookup operation (locating a particular node in the tree) is fast and simple
- Time: O(log(n)) for a balanced binary search tree
- Worst case is O(n) where each node has only one child and it becomes a linked list
- usually it happens
- Insert/Delete are also O(log(n)) time in BSTs
- you can obtain the smallest element by following all the left children and the largest element by following all the right children
- Nodes can be printed in order in O(n) time
- Given a node, you can even find the next highest node in O(log(n)) time.
