Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   
   HTML   
   CSS   
   JAVA SCRIPT   
   JQUERY   




BINARY SEARCH TREE


So, far we have looked at Binary Trees(i.e. A tree that can have maximum 2 children).


Now, we will use the Binary Trees and tweak its feature a little, so that it becomes quite effective for searching an element in it. And will call it a 'Binary Search Tree'.


The Binary Search Tree has two important properties :


  1. All Nodes in the Left Sub-Tree must be less than the Root element and the Right Sub-Tree.
  2. All Nodes in the Right Sub-Tree must be greater than the Root element and the Left Sub-Tree.

Let us understand the above properties with the below example,


java_Collections

As we can see that '16' is the root element.


And the Left Sub-Tree of '16' is :


java_Collections

And the Right Sub-Tree of '16' is :


java_Collections

Now, according the first property, all Nodes in the Left Sub-Tree must be less than the Root element and the Right Sub-Tree.


So, let us pick any element from the Left Sub-Tree. Say, we have picked the element '13'.


java_Collections

Now, if we compare '13' with the root element '18'. We can see that '13' is less.


Similarly, if we compare '13' with all the elements of the Right Sub-Tree. There are three elements 25, 18 and 30.


java_Collections

And '13' is less than all the three elements of the Right Sub-Tree.


Now since, we have checked the first property. Let us check the second property, i.e. All Nodes in the Right Sub-Tree must be greater than the Root element and the Left Sub-Tree.


So, as usual, let us pick any element from the Right Sub-Tree.


The Right Sub-Tree is,


java_Collections

Let us take the element '18'. And let us compare '18' with the root element '16'.


And '18' is greater than the root element '16'.


Now, let us compare '18' with the elements of the Left Sub-Tree. The elements in the Left Sub-Tree are 10, 2 9 and 13.


java_Collections

And '18' is greater than all the elements of the Left Sub-Tree.


Now, let us take any Sub-Tree. Say, we will take the Right Sub-Tree.


java_Collections

Now, if we consider '10' as the root element. All the elements of the Left Sub-Tree (i.e. 2 and 9) is less than '10'.


And the element in the Right Sub-Tree(i.e. 13) is greater than the root element '10'.


So, above properties applies to the the entire 'Binary Search Tree'.



How to find the Smallest and Largest element from the Binary Search Tree ?


Let us take the same Binary Search Tree to find the Smallest and Largest element.


java_Collections

The Smallest element is always at the end of the left most Sub-Tree i.e. 2.


java_Collections

And the Largest element is always at the end of the right most Sub-Tree i.e. 30.


java_Collections


How to add an element to the Binary Search Tree ?


So, we have the below Binary Search Tree :


java_Collections

Now, let us say, we will try inserting the element '3' to the above Binary Search Tree.


And as per the properties of the Binary Search Tree, all elements less than the root element should be on the left Sub-Tree and all elements greater than the root element should be on the right Sub-Tree.


With these properties in mind, let us try inserting the element '3' to the Binary Search Tree.


So, the first thing we do is, compare '3' with the root element '16'.


java_Collections

And find that '3' is less than '16'. So, as per the property of the Binary Search Tree, '3' should be somewhere in the Left Sub-Tree.


And we compare '3' with the first element of the Left Sub-Tree i.e. 10.


java_Collections

Even in this case we find that '3' is less than '10'. So, '3' should sit somewhere in the Left Sub-Tree of '10'.


And the first element in the Left Sub-Tree of '10' is '2'.


So, we compare '3' with '2'.


java_Collections

Now, in this case, '3' is greater than '2'. So, it will sit somewhere in the Right Sub-Tree of '2'.


And the first element in the Right Sub-Tree of '2' is '9'.


So, we compare '3' with '9'.


java_Collections

In this case we find that '3' is less than '9'. So, it sit somewhere to the left side of '9'.


And since, there is no elements in the left side of '9'.


So, '3' goes and sits there finally.


java_Collections


How to delete an element from the Binary Search Tree ?


So, we have the below Binary Search Tree :


java_Collections

Let us say, we want to delete the element '18' from the above Binary Search Tree.


java_Collections

Now since, '18' has no children, it can be deleted and no further adjustments needs to be done in the above Binary Search Tree.


java_Collections

Next, let us say we want to delete the root element '16'.


So, we will delete the root element '16' first.


java_Collections

Now, the question would be, who would fill the place of the deleted root element i.e. '16'?


Now, let us take the element from the Left Sub-Tree to fill its place. So, as we know that all the elements that are less than the root element are on the Left Sub-Tree.


Below is the Left Sub-Tree :


java_Collections

Now, if we take the largest element from the above Left Sub-Tree and place it as the root element.


So in this case, the root element of the above Left Sub-Tree is '10'. And as we know all the elements at the right of the Binary Search Tree should be greater than the root.


And since, there is just one element in the Right Sub-Tree of 10 i.e. '13'. So, '13' can be placed at the place of the root element.


And '13' is called as the 'Inorder Successor'.


java_Collections


How to search an element from the Binary Search Tree ?


Once again, let us take the below Binary Search Tree,


java_Collections

Let us say, we want to search the element '2' from the above Binary Search Tree.


So, as we have done in the above case, we would compare the element '2' with the root element '16'.


java_Collections

And find that '2' is less than '16'. So, the element '2' should be somewhere in the Left Sub-Tree.


So, we would compare '2' with the first element of the Left Sub-Tree i.e. 10.


java_Collections

Now, '2' is less than '10'. So, '2' should be somewhere in the Left Sub-Tree of '10'.


So, we compare '2' with the first element of the Left Sub-Tree of '10'.


java_Collections

And the first element of the Left Sub-Tree of '10' is '2'. So, we find the element '2' in this location. And our search is complete.



Running Time of Binary Search Tree


Best Case to Insert an element in Binary Search Tree : O(log n)


Average Case to Insert an element in Binary Search Tree : O(log n)


Worst Case to Insert an element in Binary Search Tree : O(n)


Best Case to Delete an element from Binary Search Tree : O(log n)


Average Case to Delete an element from Binary Search Tree : O(log n)


Worst Case to Delete an element from Binary Search Tree : O(n)


Best Case to Search an element in Binary Search Tree : O(log n)


Average Case to Search an element in Binary Search Tree : O(log n)


Worst Case to Search an element in Binary Search Tree : O(n)