Trees Unveiled - Part 1 (BST intro)

Probably we are very much acknowledged about binary search.The search technique which allows us to find data in logarithmic time.Which is efficient enough.Even searching through millions of data doesnt even take so long.

If searching by binray search approach really working well then why do we need another "Tree" appraoch to solve similar problems ??

Before jumping into the quick answer lets know about binary search tree.Every node in binary search tree or BST had a value of course and 2 sides(left hand , right hand).The rule is left hand side node always having value lesser than the parent node and right hand side always having value greater than parent node.When its equal programmer can choose either.

A BST looks kinda like this.

So how to search through it ?

Suppose youre searching for the value 8.Lets see the simulation

If you observed it then you probably found out that every single step we are reducing the search space by half.It clearly depict that our BST search complexity is O(log2(n)). Which is equivalent to binary search.

Then what's the benefit of it ?

Yeah , benefit tooks place when we consider insertion along with search.In an typical array or sequential data structure contain a rigid chunks of data where we can't insert as our wish.

Lets say , An array "Numbers" looks like this in memory

Those are sequential data resides in a chunk.its really become expensive when we try to insert new value somewher into this.Let me show you how.

Suppose we want to insert 5 in the array in correct position with along with maintaining the sorted status of it.

So in a situation like this at worst case you may have to shift all the values of the array then insert the new value.which is complied complexity of O(n).Not so good.

Here Binary search Tree(BST) comes in rescue.Let's see how BST insertion works

so yes now insertion is taking places in log2(n) time.we can insert ,search in log2(n) time.which is pretty good.

A nice example from

Reference : Introduction to algorithm Thomas H. Cormen,?Charles E. Leiserson,?Ronald L. Rivest,?Clifford Stein