A BST is a binary tree that is built in such way that the tree is always sorted. This means the left child node has a value less than or equal to the parent node value, and right child node will have the value greater than the parent node value. So, whenever we need to search a value, either we will search left or search right. As it is sorted, we have to search one part of the tree, not both, and this continues recursively. For its dividing nature, the searching becomes very fast, and we can achieve logarithmic complexity for the search. For example, if we have n number of nodes, we will search either the first half or second half of the nodes. Once we are in the first or second half, we can divide it again into two halves, which means our half now becomes a quarter, and it goes on and on until we reach the final node. As we are not moving to each node to search, it is not going to take O(n) complexity for the operation. In the next chapter, we will do the complexity analysis of a binary search and will see why the binary search tree has a search complexity of O(log n). Unlike the binary tree, we cannot add any node to or remove any node from the tree without reconstructing the BST properties.

If node X has two children, then the successor of node X is the smallest value that belongs to the tree, which is greater than the value of X. In other words, the successor is the minimum value of the right subtree. On the other hand, the predecessor is the maximum value of the left subtree. Now, we will focus more on the different operations of a BST and the steps we need to consider to perform those operations correctly.

Here are the operations of a BST.