It is a binary tree where each node has a key and an associated value which satisfies the following restriction :
- The key in any node is larger than the keys in all nodes in that node's left subtree
- The key in any node is smaller than the keys in all nodes in that node's right subtree.
In-order Property: The idea of a binary search tree is to store data according to an order, so that it can be retrieved very efficiently. An in-order traversal of the binary tree results in a sorted sequence.
- The running times of algorithms on binary search trees depend on the shapes of the trees, which, in turn, depends on the order in which keys are inserted.
- If we make sure that tree remains balanced after every insertion and deletion, then we can guarantee search, insert, delete and other basic operations in O(log n) time complexity.