Threaded Binary Trees
A binary tree can be represented using array representation or linked list representation. When a binary tree is represented using linked list representation, the reference part of the node which doesn't have a child is filled with NULL pointer. In any binary tree linked list representation, there are more number of NULL pointers than actual pointers. Generally, in any binary tree linked list representation, if there are 2N number of reference fields, then N+1 number of reference fields are filled with NULL ( N+1 are NULL out of 2N ). This NULL pointer does not play any role except indicating that there is no link (no child).
A. J. Perlis and C. Thornton have proposed new binary tree called "Threaded Binary Tree", which makes use of NULL pointers to improve its traversal process. In threaded binary tree, NULL pointers are replaced by references of other nodes in the tree. These extra references are called as threads.
Threaded Binary Tree is also a binary tree in which all left child pointers that are NULL (in Linked list representation) points to its in-order predecessor, and all right child pointers that are NULL (in Linked list representation) points to its in-order successor.
If there is no in-order predecessor or in-order successor, then it points to the root node.
Consider the following binary tree...
To convert the above example binary tree into threaded binary tree, first find the in-order traversal of that tree...In-order traversal of above binary tree...
H - D - I - B - E - A - F - J - C - G
When we represent the above binary tree using linked list representation, nodes H, I, E, F, J and G left child pointers are NULL. This NULL is replaced by address of its in-order predecessor respectively (I to D, E to B, F to A, J to F and G to C), but here the node H does not have its in-order predecessor, so it points to the root node A. And nodes H, I, E, J and G right child pointers are NULL. This NULL pointers are replaced by address of its in-order successor respectively (H to D, I to B, E to A, and J to C), but here the node G does not have its in-order successor, so it points to the root node A.
Above example binary tree is converted into threaded binary tree as follows.
In the above figure, threads are indicated with dotted links.