Binary Search Tree is a special type of data structure that supports many dynamic set(collection) operations. Purpose of this short blog post is to explain what is a randomly-built  Binary Search tree and why it is important. Readers of this post are expected have a basic understanding on Binary Search trees.

In Binary Search trees, almost all the basic operations such as insertion, deletion and search are O(h). In here h is the height of the resulting binary search tree. But the problem is height of the tree depends on the order of insertion.

As an example, lets take the number sequence(2,5,5,6,7,8) need to be inserted into a binary search tree. If we insert them in the order of (2,5,7,6,8,5), resulting tree will look like this. (Figure 1)

Figure 1

If we insert them in the order of (6,7,5,2,8,5), Resulting tree will look like this. (Figure 2)

Figure 2

Now It is clear that height of the tree will depend on the order of insertion in the tree construction process. Minimum height of a tree with n nodes is log(n). So our target should be building a tree with the height of log(n) for any given sequence of numbers.

It is true that we can sort the number sequence and declare algorithm that first insert middle elements and then gradually come to two sides inserting elements in the two boundaries. But such algorithms needs sorting first which makes the progress more time complex.

As an solution to that problem randomly-built trees are introduced. In that method, first elements that needs to insert are permuted randomly. Then those numbers are inserted to the tree in that order. Expected height of the tree is log(n). This does not guarantee that this will always gives optimal tree with minimum height. But there is a high probability that this tree is a balanced tree with log(n) height compared to inserting normal order. This StackExchange Answer tries to prove that it will give a time complexity of log(n).

This method is not applicable for some scenarios such as when not all the number are present at the start of the tree building. But still this can be used as an efficient way to build balanced trees when all numbers are presented at the beginning.

(In this blog post, tree images (figure 1 and 2) are created with the help of this tool )