Threaded storage representation of binary tree
Basically in normal binary tree representation there are two links i.e. left and right link. Right link of node is points to address of right sub-tree and left link of node is points to address of left sub-tree. But when there is no sub-tree on its right or left than that link is replaced by NULL i.e. if left sub-tree is absent then left link of node is replaced by NULL, if right sub-tree is absent then right link of node is replaced by NULL.
When there is big tree having large number of nodes than it is wastage of memory while placing NULL. To Solve this wastage of memory problem threaded binary tree is introduced in which left or right link of nodes are replaced by address of other node according to particular traversal technique on which it is formed, these links are known as threads.
Thread link is denoted with dashed arrow.Head node serves as predecessor and successor of the first and last nodes with respect to particular traversal technique.
Normally in binary tree the valid pointers that pointed to left sub-tree or left sub-tree as considered as positive values or non-negative values. But in case of threaded binary tree threads are denoted by negative values because it is easily differentiated by regular pointers.
Before first node of tree is created head node is created, which is displayed as
Consider following example
a tree having 7 nodes are displayed as follows
Now normal linked list representation are displayed here having NULL values.
Now to form threaded representation of above binary tree we have to form in-order traversal of above tree, which is CBAEFDG
Now its time to making threads.
1. Left link of node C is points to head and right link of node G points to head node because there is no node in in-order traversal
2. Right link of node C is points to address of node B because node B succeeds node C
3. Left link of node F is points to address of node E because node E precedes node F So like this all the NULL link is replaced by address of other node according to in-order traversal.
Threaded binary tree of main tree is presented as
1. By using threaded binary tree traversing of tree is very faster as compared to normal representation of binary tree.
2. Other advantage of using threaded binary tree is anyone can easily find successor or predecessor of any node.
1. One of the disadvantage using threaded binary tree is we can not share common sub-tree.
2. It is possibly to confuse which is threads and which are actual link.