Binary search trees allow binary search for fast lookup, addition, and removal of data items, and can be used to implement dynamic sets and lookup tables. Since the nodes in a BST are laid in such as way that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.
The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree; several variations of the binary search tree can be built with guaranteed worst-case performance. The basic operations include: search, traversal, insert and delete. BSTs with guaranteed worst-case complexities perform better than an unsorted array, which would require linear search time.
The complexity analysis of BST shows that, on average, the insert, delete and search takes {\displaystyle O(\log n)}O(\log n) for {\displaystyle n}n nodes. In the worst case, they degrade to that of a singly linked list: {\displaystyle O(n)}O(n).
