A Binary tree nodes may have at most two children. But if they have only one children, or no children, the link part in the linked list representation remains null. Using threaded binary tree representation, we can reuse that empty links by making some threads.

It makes inorder traversal faster and do it without stack and without recursion. 

There are two types of threaded binary trees.

1. Single Threaded 

Each node is threaded towards either left or right means in-order predecessor or successor. Here, all right null pointers will point to inorder successor or all left null pointers will point to inorder predecessor.

2. Double threaded

Each node is threaded towards either left and right means in-order predecessor and successor. Here, all right null pointers will point to inorder successor and all left null pointers will point to inorder predecessor.

C++ Program to implement Threaded Binary Tree

#include<bits/stdc++.h> using namespace std; 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; }; struct Node* insert( struct Node* root, int key) { Node *ptr = root; Node *parent= NULL; // parent of data to be inserted while(ptr != NULL) { // if data already exists if( ptr->data == key) { cout<<"Duplicate entry !\n"; return root; } parent = ptr; // update parent node //moving on left subtree if(key < ptr->data) { if(ptr -> lthread == false) { ptr = ptr -> left; } else break; } //moving on right subtree if(key > ptr->data) { if(ptr -> rthread == false) { ptr = ptr -> right; } else break; } } //creating a new node Node *temp= new Node; temp -> data = key; temp -> lthread = true; temp -> rthread = true; if(parent == NULL) { root = temp; temp -> left = NULL; temp -> right = NULL; } else if(key < parent -> data ) { temp -> left = parent -> left; temp -> right= parent; parent -> lthread = false; parent -> left = temp; } else { temp -> left = parent; temp -> right= parent -> right; parent -> rthread = false; parent -> right = temp ; } return root; } //returns inorder successor using rthread struct Node *inordersuccessor (struct Node *ptr) { //if rthread is true, we can quickly find it if( ptr -> rthread == true ) return ptr->right; //else return leftmost child of right subtree else { ptr = ptr -> right; while(ptr -> lthread == false) ptr = ptr -> left; return ptr; } } //printing inorder of threaded tree void inorder ( struct Node *root ) { if( root == NULL) cout<<"Tree is empty\n"; else{ //reach leftmost Node Node *ptr = root; while( ptr -> lthread == false) ptr = ptr -> left; // print successor of each node one by one while( ptr != NULL) { cout<<ptr -> data<<" "; ptr=inordersuccessor(ptr); } cout<<"\n"; } } int main() { struct Node *root = NULL; root = insert(root, 2); root = insert(root, 10); root = insert(root, 13); root = insert(root, 50); root = insert(root, 12); root = insert(root, 14); root = insert(root, 71); root = insert(root, 66); inorder(root); return 0; }

OUTPUT

2 10 12 13 14 50 66 71