HA-BLOG

Threaded Binary Trees & It's Applications

(Ref. https://www.codingninjas.com)

Contents

• What is Threaded Binary Tree?
• Why Threaded Binary Tree?
• Types of Threaded Binary Trees
• Advantages
• Disadvantages
• Applications of Threaded Binary Trees
• Conclusion
• References

---

What is Threaded Binary Tree?

Threaded binary tree is a data structure derived from a simple binary tree. But, here's the twist, Threaded Binary Trees use different strategy to deal with the null pointers left at the leaf nodes of a regular binary trees by setting the null pointers of leaf node to be set to inorder predecessor or inorder successor.

Node representation :-

    //Single threaded
    struct node{
        int data ;
        node *left ;
        node *right ;
        bool rThread ;
    }
                    

    // double threaded
    struct node{
        int data ;
        node *left ;
        node *right ;
        bool lThread ;
        bool rThread ;
    }
                    

---

Why Threaded Binary Tree

• Normal binary tree use stacks and queues for traversal which uses huge amount of memory used for traversal.
• Apart from this, there are n+1 number of NULL pointer as the summation of all the right and left pointers of leaf nodes of binary tree that uses memory very inefficiently.
• To overcome this, we use Threaded Binary trees where the NULL pointers of right and left pointers of leaf node are entered with some meaningful information of to inorder predecessor or inorder successor as mentioned earlier which helps in proper memory usage and faster traversal of the tree.

---

Types of Threaded Binary Trees

There are two types of threaded binary trees :-

1. Single Threaded Binary Tree

In this type of threaded binary tree, the right pointer of tree node points to next inorder successor node of the tree.

Fig :- Single Threaded Binary Tree

2. Double Threaded Binary Tree

In this type of binary tree, both the right and left pointers of threaded binary point to the next inorder successor and predecessor respectively.

Fig :- Double Threaded Binary Tree

---

Advantages

Advantages of Threaded Binary Trees :-

• No need for stacks or recursion:
  Threaded binary trees do not require a stack or recursion for traversal as binary trees do.
• Optimal memory usage:
  Threaded Binary Tree reduces memory wastage. In normal binary trees, memory is wasted as Left and Right of the node contains NULL. But with threaded binary trees, we are overcoming the problem by storing it's inorder predecessor or successor.
• Time complexity:
  In-order traversal in a threaded binary tree is faster because we get directly to the next node in O(1) time than a normal binary tree that takes O(Height).
• Backward traversal:
  In a double-threaded binary tree, even a backward traversal is possible.

---

Disadvantages

Disadvantages of Threaded Binary Trees :-

• Complicated insertion and deletion:
  By storing the inorder predecessor or successor for the node with a null left or right pointer, we make the insertion and deletion of a node more time-consuming and a highly complex process compared to binary trees.
• Extra memory usage:
  Additional memory is used in the form of right Thread and left Thread variables to differenciate between a thread from an ordinary link. (However, there are more efficient methods to differentiate between thread and an ordinary link).

---

Applications of Threaded Binary Trees

Few Applications of Threaded Binary Trees are :-

• The idea of threaded binary trees is to make inorder traversal of the binary tree faster and do it without using any extra space, so sometimes in small systems where hardware is very limited. Threaded binary tree are used for better efficiency of the software in a limited hardware space.
• It is possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack. This can be useful where stack space is limited, or where a stack of parent pointers are unavailable.
• A Threaded Binary Tree is a binary tree in which every node that does not have a right child and have a THREAD in actual sense a link to its INORDER successor. As a result of this threading we avoid the recursive method of traversing a Tree which uses of stacks and consumes a greater of memory and time.

---

Conclusion

Threaded Binary trees play a major role in data structures and has various plus points as compared to regular binary trees, but there are a few setbacks too, for eg as mentioned, complex implementation. Thus, threaded binary trees are to be used where space complexity plays a vital role irrelevant of the insertion and deletion operations and traversal acts as the most prominent aspect of all.
Thankyou! We hope you enjoyed reading! Do like share and Comment!

---

References

• Research Papers
  • Analyisis of Algorithm on threaded trees
  • Binary Search Tree Balancing Methods: A Critical Study
• Articles
  • https://www.geeksforgeeks.org/threaded-binary-tree/
  • https://www.javatpoint.com/threaded-binary-tree
  • https://iq.opengenus.org/threaded-binary-tree/
  • https://www.sarthaks.com/447945/threaded-binary-trees-advantages-disadvantages-threaded-binary-trees-binary-search-trees

---

Prepared By:-

• Ajinkya Mahajan
• Aditya Bodhankar
• Riya Dhakalkar
• Aishwarya Pujari
• Diksha Prasad
• Shivani Mahajan