Threaded Binary Tree - Concept Explained

In the linked representation of a binary tree, additional space is required to store the two links of each node.
For leaf nodes, these fields always have nil values as there are no left or right sub-trees present.
To remove this drawback of memory wastage, the concept of threaded binary tree was developed. In this type of tree, the empty links are replaced by pointers, called threads which point to some other node of the tree.

If the left child of a node of a tree is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just before that node, when the tree is traversed in inorder.

Similarly, if a right child of the node is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just after that node, when the tree is traversed in inorder.
Such threads are called inorder threads.
We also have preorder and postorder threads.

The left thread gives predecessor and the right thread gives successor node.

The node of a threaded binary tree can be declared as:

enum boolean
{
int false = 0;
int true = 1;
};
struct threadedtree
{
enum boolean left;
struct threadedtree *leftchild;
int data;
enum boolean right;
struct threadedtree *rightchild;
}