Threaded Binary Tree - Concept Explained

In the linked representation of a binary tree, additional space is required to store the two links of each node.
For leaf nodes, these fields always have nil values as there are no left or right sub-trees present.
To remove this drawback of memory wastage, the concept of threaded binary tree was developed. In this type of tree, the empty links are replaced by pointers, called threads which point to some other node of the tree.

If the left child of a node of a tree is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just before that node, when the tree is traversed in inorder.

Similarly, if a right child of the node is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just after that node, when the tree is traversed in inorder.
Such threads are called inorder threads.
We also have preorder and postorder threads.

The left thread gives predecessor and the right thread gives successor node.

The node of a threaded binary tree can be declared as:

enum boolean
{
int false = 0;
int true = 1;
};
struct threadedtree
{
enum boolean left;
struct threadedtree *leftchild;
int data;
enum boolean right;
struct threadedtree *rightchild;
}

Replies

  • Sachin Jain
    Sachin Jain
    Hey AbraKaDabra Thanks for this topic...its really good and helpful.
    I had never observed about the wastage due null pointers in leaf nodes.
    -
    Can you please explain this line:-
    If the left child of a node of a tree is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just before that node, when the tree is traversed in inorder.
    What is the advantage of doing so ?

    Any appliaction of threaded binary trees ?

    Thanks in advance...
  • Ankita Katdare
    Ankita Katdare
    Good Question. Following are the advantages of using threaded binary tree:

    1) The traversal operation is faster than that of its unthreaded version, because with threaded binary tree non-recursive implementation is possible which can run faster and does not require the botheration of stock management.

    2) We can efficiently determine the predecessor and successor nodes starting from any node. A stack is required to provide upward pointing information in the tree whereas in a threaded binary tree, without having to incur the overload of using a stack mechanism the same can be carried out with the threads.

    3) Any node can be accessible from any other node. Threads are usually more to upward whereas links are downward. Thus in a threaded tree, one can move in either direction and nodes are in fact circularly linked. This is not possible in unthreaded counter part because there we can move only in downward direction starting form root.

    4) Insertion into and deletions from a threaded tree are all although time consuming operations(since we have to manipulate both links and threads). But these are very easy to implement.#-Link-Snipped-#
  • Sachin Jain
    Sachin Jain
    Thanks AbraKaDabra very nicely explained....😀

You are reading an archived discussion.

Related Posts

Load Rejection Test (Governor Test) The purpose of Turbine Load Rejection Test is to verify and demonstrate the governor function to sustain a load rejection in order to prevent the...
Does anybody here taken a subject strength of materials???😒
[video=youtube;ThMTmWnE6hM]https://www.youtube.com/watch?v=ThMTmWnE6hM&feature=related[/video]
[video=youtube;4Vg-ftPI8TM]https://www.youtube.com/watch?v=4Vg-ftPI8TM&feature=related[/video]
[video=youtube;8yv5owU36I4]https://www.youtube.com/watch?v=8yv5owU36I4&feature=related[/video]