A threaded binary tree is a binary tree variant that facilitates traversal in a particular order.An entire binary sort 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 descendant,so no other node can be reached given only a pointer to a leaf node of course that includes the desired"next"node.A nthreaded tree adds extra information in some or all nodes,so the "next"node can be found quickly.it can also be traversed without recursion and the extra storage that requires.
"A binary tree is threaded by making all right child pointers that would normally be null point to the in-order successor of the node,and all left child pointers that would normally be null point to the in-order predecessor of the node." this definition assumes order is the same as in-order traversal of the tree.however,pointers can instead(or in addition) be added to tree nodes,rather than replacing linked lists thus defined are also commonly called "threads",and can be used to enable traversal in any order desired.
