Threaded Binary Tree.pptx

Threaded Binary Tree

1. Presentation on : Threaded Binary Tree Student Name: MOULI MANDAL Student Code: BWU/MCA/22/095 Reg. No. : 22012006227 of 2022-2023 University Roll No. : 22010201087 Course Name: Data Structures and Algorithms Course Code: MCA101 Semester: I Programme Name: Master of Computer Applications

2. Index How the concept of Threaded Binary Tree came? What is a Threaded Binary Tree? Types of Threaded Binary tree a) Single-Threaded Binary Tree b) Double-Threaded Binary Tree Advantages of Threaded Binary Tree Disadvantages of Threaded Binary Tree

3. How the concept of Threaded Binary Tree came? Many nodes present in this tree hold a NULL value in their left or right child pointer (which are denoted by sketched fields) The space occupied by these null values can be used to store some kind of valuable information. One possible way to utilise this space is to have a special pointer that points to nodes higher in the tree. These special pointers are called threads.

4. What is a Threaded Binary Tree? A variant of a normal Binary Tree. The nodes will store the in-order predecessor/successor instead of storing NULL in the left/right child pointers. The leftmost and the rightmost child pointer of a tree always points to null as their in-order predecessor and successor do not exist.

5. Types of Threaded Binary tree Threaded Binary Tree Single-Threaded Binary Tree Double-Threaded Binary Tree

6. Single-Threaded Binary Tree If a node has a right null pointer, then this right pointer is threaded towards the in-order successor’s node if it exists Node Structure of Single-Threaded Binary Trees: struct Node{ int value; Node* left; Node* right; bool rightThread; }

7. Double-Threaded Binary Tree The left null pointer of a node is made to point towards the in-order predecessor node and the right null pointer is made to point towards the in-order successor node. Node Structure of Double-Threaded Binary Trees: struct Node{ int value; Node* left; Node* right; bool rightThread; bool leftThread; }

8. Advantages of Threaded Binary Tree No need for stacks or recursion Optimal memory usage Time complexity Backward traversal

9. Disadvantages of Threaded Binary Tree Complicated insertion and deletion Extra memory usage

10. THANK YOU