- The wasted NULL links in the binary tree storage representation can be replaced by threads.
- A binary tree is threaded according to particular traversal order. e.g.: Threads for the inorder traversals of tree are pointers to its higher nodes, for this traversal order.
- If left link of node P is null, then this link is replaced by the address of its predecessor.
- If right link of node P is null, then it is replaced by the address of its successor
- Because the left or right link of a node can denote either structural link or a thread, we must somehow be able to distinguish them.
- Method 1:- Represent thread a –ve address.
- Method 2:- To have a separate Boolean flag for each of left and right pointers, node structure for this is given below,
- LTHREAD = true = Denotes leaf thread link
- LTHREAD = false = Denotes leaf structural link
- RTHREAD = true = Denotes right threaded link
- RTHREAD = false = Denotes right structural link
- Head node is simply another node which serves as the predecessor and successor of first and last tree nodes. Tree is attached to the left branch of the head node
| Advantages | Disadvantages |
|---|---|
| Inorder traversal is faster than unthreaded version as stack is not required | Threaded trees are unable to share common subtrees |
| Effectively determines the predecessor and successor for inorder traversal, for unthreaded tree this task is more difficult | If –ve addressing is not permitted in programming language, two additional fields are required |
| A stack is required to provide upward pointing information in tree which threading provides | Insertion into and deletion from threaded binary tree are more time consuming because both thread and structural link must be maintained |
| It is possible to generate successor or predecessor of any node without having over head of stack with the help of threading |
Fully In-threaded binary tree of given binary tree
