a threaded binary tree is a binary tree variant that facilitates traversal in a particular order.
An entire binary search tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so given only a pointer to a leaf node no other node can be reached. A threaded tree adds extra information in some or all nodes, so that for any given single node the "next" node can be found quickly, allowing tree traversal without recursion and the extra storage (proportional to the tree's depth) that recursion requires.
Types of Threaded Binary Tree
There are two types of threaded binary tree:
Single Threaded Binary Tree
Double Threaded Binary Tree
Single Threaded Binary Tree: Here only the right NULL pointer are made to point to inorder successor.
Double Threaded Binary Tree: Here both the right as well as the left NULL pointers are made to point inorder successor and inorder predecessor respectively. (here the left threads are helpful in reverse inorder traveral of the tree )
