Threaded Binary Trees Structure,Types and Inorder Traversal

Threads :

In my previous post I discussed about preorder , postorder and inorder binary tree traversals used stacks and level order traversals used queues as an auxiliary data structure . I highly recommend to know the basic binary tree traversals from the last post . 
In this article I will discuss new traversal algorithms which do not need both stacks and queues and such traversal algorithms and called Threaded Binary Tree Traversals or stack/queue less traversals .

Issues with regular Binary Tree Traversals :

• The storage space required for stack and queue is large .
• The majority of pointers in any binary tree are NULL . For example a binary tree with n nodes has n+1 NULL pointers and these were wasted .
• It is difficult to find successor node ( preorder ,inorder and postorder successors ) for a given node  .

Motivation for Threaded Binary Trees :

To solve these problems , one idea is to store some useful information in NULL pointers . If we observe previous traversals carefully , stack/queue is required because we have to record the current position in order to move to right subtree after processing the left subtree . If we store the useful information in NULL pointers  then we don't have to store such information in stack / queue. The binary trees which store such information in NULL pointers are called Threaded Binary Trees .
The next question is what to store ?
The common convention is pust predecessor/successor information . That means , of we are dealing with preorder traversals then for a given node . NULL left pointer will contain preorder predecessor information and NULL right pointer will contain preorder successor information . These special Pointers are called Threads .

Classifying Threaded Binary Trees :

The classification is based on whether we are storing useful information in both NULL pointers or only on one of them ,

1. If we store predecessor information in NULL left pointers only then we call such binary trees as Left Threaded binary trees .
2. If we store successor information in NULL right pointers only then we call such binary trees as right threaded binary trees .
3. If we store predecessor information in NULL left pointers only then we call such binary trees as Fully threaded binary trees or simply threaded binary trees . 

Types of Threaded Binary Trees :

Based on above forms we get three representations for threaded binary trees .

1. Preorder Threaded Binary Trees : NULL left pointer will contain Preorder predecessor information and NULL right pointer will contain preorder successor information .
2. Inorder Threaded Binary Trees : NULL left pointer will contain Inorder predecessor information and NULL right pointer will contain Inorder successor information .
3. Postorder Threaded Binary Trees : NULL left pointer will contain Postorder predecessor information and NULL right pointer will contain Postorder successor information . 

Threaded Binary Tree Structure :

Any program examining the tree must be able to differentiate between a regular left/right pointer and a thread . To do this we use two additional fields onto each node giving us for threaded trees nodes of the following form .

 struct threadedbtnode
{
    struct threadedbtnode *left;
    int Ltag;
    int data;
    int Rtag;
    struct threadedbtnode *right;
};

As an example let us try representing a tree in inorder threaded binary tree form . The below tree shows how an inorder threaded binary tree will look like . The dotted arrows indicated the threads . If we observe the left pointer of left most node (2) and right pointer of right most node node (31) are hanging.

Inorder Traversal of a Threaded Binary Tree :

To find inorder successor of a given node without using a stack , assume that the node for which we want to find the inorder successor is P.
Strategy : If P has a no right subtree then return the right child if P. If P has right subtree then return the left of the nearest node whose ledt subtree contains P.

struct threadedbtnode * inordersuccessor(struct threadedbtnode *P)
{
    struct threadedbtnode *position;
    if(P->Rtag==0) return P->right;
    else
    {
        position =P->right ;
        while(position->Ltag==1)
            position=position->left;
        return position;
    }
};

Time complexity : O(n)
space complexity : O(1)
Inorder Traversal in Inorder Threaded Binary Tree : We can start with dummy node and call inordersuccessor() to visit each node until we reach dummy node .

void inordertraversal(struct threadedbtnode *root)
{
    struct threadedbtnode *P=inordersuccessor(root);
    while(P!=root)
    {
        P=inordersuccessor(P);
        printf("%d",P->data);
    }
}

Time complexity : O(n)
space complexity : O(1)

Inserting a Node into a Threaded Binary Tree 

For simplicity let us assume that there are two nodes P and Q and we want to attach Q to right of P. For this we will have 2 cases .
1. Node P does not has right child : In this case we just need to attach Q to P and change its left and right pointers .

2. Node P has right child (say R) : In this case we need to traverse R's left subtree and find the left most node and then update the left and right pointer of that node . 

Final Words !

If I had missed anything Please get it to me through comments . Also share your ideas , Logic and Programs through comments .