Algorithm for Searching a Node in Binary Search Tree

Binary Search Tree is a Binary Tree which satisfy following rules 

• Left child or node has a value or data less than the root node value .
• Right child has a value grater then root node value or data .

The following Binary Search tree which satisfies above two rules . Let the data entered be 8 , 3 , 10 ,1 , 6 , 14 , 4 ,7 , 13  .

Root node data is 8 . All the nodes in the left sub tree of the root have a value less than 8 . Similarly all the nodes in the right of the sub tree of the root node have values greater than 8 . The same holds for all other subtrees as well .

Also check : Program for Linear search in C++

Algorithm for Searching a Node in Binary Search Tree :

The search operation in a binary search tree refers to the process of searching for a specific value in the tree .
To search a particular value in binary search tree , you need to perform the following steps :

1. Make current Node point to the root node .

2. If current Node is NULL : 

• Display "Not Found"
• Exit 

3. Compare the value to be searched with the value of current Node . Depending on the result of the comparison , there can be 3 posibilities :

• If the value is equal to the value of current Node:

         3.1.1. Display "Found"

         3.1.2. Exit

• If the value is less than the value of the current Node :

         3.2.1. Make current Node point to its left child .

         3.2.2. Go to step 2 .  

• If the value is Greater then the value of current Node :

         3.3.1. Make current Node point to its right child.

         3.3.2. Go to step 2 . 

 

Also check : Program for Bubble sort in c++           

    

From the above algorithm you can see after every comparison , the number of elements to be searched reduces to half . As a result, binary search tree provides quick access to data . The timing complexity for Searching an element in Binary search tree is order of logn O(logn) .

If I have missed anything please Get it to me through comments . Also share your ideas and Logics through comments .