A binary search tree (BST), also called an ordered or sorted Binary Trees, is a rooted binary tree (up to two children) data structure with the key of each internal node being greater than all the keys in the respective node’s left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is [linear] with respect to the height of the tree.
Binary search trees allow for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm ()
