C++ Program for searching in Threaded Binary Tree














































C++ Program for searching in Threaded Binary Tree



we have already seen some operation on Threaded binary tree like:

1. Insertion and Displaying : javascript:nicTemp();
2. Deletion: javascript:nicTemp();
3. Finding inorder Successor: javascript:nicTemp();

Searching Operation
Search operation is pretty simple in Threaded Binary tree, we just need to follow a simple algorithm

   If search key == root 
          stop algorithm
   Else-if search key < root 
          go to left thread
   If search key > root 
          go to right thread

Node of threaded binary tree is represent as
struct Node { struct Node *left, *right; int data; bool lthread; //false if left pointers is a thread; bool rthread; //false if right pointer is a thread; };

C++ Program for search operation

struct Node *search( struct Node *root , int key ){ Node *ptr = root ; while( ptr != null ) { if( ptr->info == key ) { // indicating that the element is found then return ptr ; } else if( ptr->info < key ) { // moving to inorder predecessor of the current node ptr = ptr->right ; } else{ // moving to inorder successor of the current node ptr = ptr->left ; } } // if element is not found then we can return nullptr indicating element not // found in the given binary search tree return nullptr ; }

Time complexity - O( logn )

  



Comments