## Threaded Binary Trees Structure,Types and Inorder Traversal

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 .

{
int Ltag;
int data;
int Rtag;
};
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)
{
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)
{
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 .