Binary Search Tree

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.