CrazyEngineers
  • Threaded Binary Tree - Concept Explained

    Ankita Katdare

    Administrator

    Updated: Oct 24, 2024
    Views: 1.5K
    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;
    }
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • Sachin Jain

    MemberDec 26, 2010

    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...
    Are you sure? This action cannot be undone.
    Cancel
  • Ankita Katdare

    AdministratorDec 26, 2010

    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-#
    Are you sure? This action cannot be undone.
    Cancel
  • Sachin Jain

    MemberDec 26, 2010

    Thanks AbraKaDabra very nicely explained....😀
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register