Threaded Binary Trees
Threaded Binary Trees are an improvement over Binary Search Trees that uses stack for iterative traversal. If a strategy is introduced such that the leaf node of a binary search tree points to its inorder predecessor or its successor, then direct links (called threads) are obtained to traverse a tree without using stack, which basically stores and retrieves the address of nodes in LIFO manner. If the left pointer of the leaf node points to its inorder predecessor, then such a threaded tree is called Left-In-Threaded Binary Tree. If the right pointer of the leaf node points to its inorder successor, then such a threaded tree is referred to as Right-In-Threaded Binary Tree. However, if both the links, left as well as right are available, then the threaded tree is called In-Threaded Binary Tree.
Threads are links or pointers that points to some node as per the sequence in inorder traversal (predecessor or successor). It is required to differentiate a link from that of a thread, we may assume to integers lflag and rflag, which may take the value of 1 or 0. If the value of lflag is 1 then it refers that the node contains a left thread, otherwise it is a link to the left subtree. Moreover, leftmost pointer in an In-Threaded Binary Tree always points to NULL since no inorder predecessor for the leftmost node is available. This thread is referred to as dangling left thread. Similar is the case with rightmost node, for which no inorder successor is available, and the thread so formed is called dangling right thread.
Function for Inorder Traversal of an In-Threaded Binary Tree:
The basic advantage of Threaded Tree is that its inorder traversal does not require the use of stack. Inorder traversal requires visiting the leftmost node, and then using right threads for the purpose of traversal. The ‘C’ function for inorder traversal is given below:
/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}
Function to insert a new node in In-Threaded Tree:
Insertion of a new node in a Threaded tree is quite similar to that of insertion in a Binary Search Tree with the only difference that at each insertion step, the inorder predecessor and inorder successor of the new node must be set accordingly and the root of newnode must be set to bear a subtree rather than a thread. The ‘C’ function to insert a new node in a Threaded Binary Tree is given below:
/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}
Function to find the Inorder Predecessor of a given node in an In-Threaded Binary Tree:
Searching and returning inorder predecessor requires comparing each node with the value whose predecessor is required. If the value is not found in the tree, error is reported. If the value is found, then a temp pointer is placed on the left of this node and shifted until it points the rightmost node. The value of the rightmost node is returned. The ‘C’ function for returning Inorder predecessor of a given node is as follows:
/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}
Function to find the Inorder Successor of a given node in an In-Threaded Binary Tree:
Searching and returning inorder successor requires comparing each node with the value whose successor is required. If the value is not found in the tree, error is reported. If the value is found, then a temp pointer is placed on the right of this node and shifted until it points the leftmost node. The value of the leftmost node is returned. The ‘C’ function for returning Inorder Successor of a given node is as follows:
/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}
Function to traverse a Left-In-Threaded Tree in Descending Order:
Traversal of a Left In Threaded Tree result in a descending order of elements. If the inorder traversal gives the result in Ascending order, then traversal using left threads may be performed such that the result is achieved in descending order. The ‘C’ function for the same is as follows:
void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%dt”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}