ডাটা স্ট্রাকচার - ৯ঃ বাইনারি সার্চ ট্রি

বাইনারি সার্চ ট্রিঃ বাইনারি সার্চ ট্রি এমন বিশেষ ধরনের ট্রি যেখানে প্রতিটা নোডের লেফট চাইল্ড ওই নোডের চেয়ে ছোট হবে এবং রাইট চাইল্ড ঐ নোডের চেয়ে বড় হবে। নীচের চিত্রে খেয়াল করো- 

ইমপ্লিমেন্টেশনঃ বাইনারি ট্রিতে আমরা ডেটা হিসেবে কিছু ইন্টেজার রাখবো-

 Algorithm of BST insert   
 1. Check the root is null or not. If the root is null then it will be the node   
 2. If root is not null then find out its parent on the basis of BST. Make sure that no node is overlapped   

Pseudo Code:

 Node *bstInsert(Node *root, Node *node)  
 {  
   Node *parentNode, *currentNode;  
   if(root == NULL)  
   {  
     root = node;  
   }  
   currentNode = root;  
   while(currentNode!= NULL)  
   {  
     parentNode = currentNode;  
     if(node->data<currentNode->data)  
     {  
       currentNode = currentNode->left;  
     }  
     else  
     {  
       currentNode = currentNode->right;  
     }  
   }  
   if(node->data<parentNode->data)  
   {  
     addLeftChild(parentNode, node);  
   }  
   else  
   {  
     addRightChild(parentNode, node);  
   }  
   return root;  
 }