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();
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