if you have done (or doing) , then you definitely got to (or will get to ) familiar with Binary Tree, and shall know (or hear) something about Threaded Binary Tree . Data Structures Motive for writing I was studying Binary Tree Data Structure , then I got to know about Threaded Binary Tree . After going through its theory part, I was curious about its implementation (Basically how insertion takes place in it ?) . So, first I googled to see if any easy( to grasp) implementation for insertion operation exists or not. But on googling , I don’t found any implementation which was easy to grasp. Then I decided to do it by my own, and After some time, I found an implementation of insertion operation which I think can be easily grasped by anyone. After that, I decided why not I write an article on it. So that it can reach to large audience. So here is the article ! Before moving on Insertion Before we move on insertion implementation in Threaded Binary Tree . I think it will be good if we discuss a little about Single Threaded Binary Tree. The idea of is to make traversal faster and do it without using any stack or recursion in Binary Trees. In Single Threaded Binary Tree , a NULL right pointer(of a node) is made to point to successor (it it exists). Single Threaded Binary Tree in-order in-order I am always mentioning its full name (Single Threaded Binary Tree) because a Double Threaded Binary Tree also exist (in this both NULL left and right pointer is made to point to in-order predecessor and in-order successor). each node (circles in picture) contains Node Contains : key; Node *left, *right; rightThread; }; // c++ // Node structure { struct Node int // value in node // stores left/right child bool // stores right Thread for node exists or not Insertion idea ! , for inserting a new node we will follow the same rule of insertion used in BST . For a node, if new value to insert is smaller than value present in node then new node(with new value) will go in left subtree of node and if new value to insert is larger value than in node , it will go in right subtree of node. First and for making thread ( on which this article mainly focuses ) we will follow following steps : Second , 1. As we can see from just above picture, that we should have the knowledge of node (in-order successor) with which we are gonna make a thread . For this , I decided to maintain a variable which stores the node with which we have to make thread. Node *successor = ; NULL ‘ ’ denotes that variable ‘ ’ does not contain any value right now. NULL successor 2. We can also see (from picture), that we need to make a thread, only if a new node is gonna inserted as left child( or left descendent) of any node . So , At the time of finding position for new node . we will store value in ‘ ’ whenever new node will be inserted as left child for a node(already present in tree) . successor (curr->key > el) { successor = curr; curr = curr->left; } // c++ // left subtree if // curr is a variable maintaining current node(already present in tree) // with which comparison is taking place // And, el is new key we have to insert // successor only contain value if new node // goes in left subtree of curr node // go left subtree 3. If new node is going to store as right child ( during finding position for new node) of a node already present in tree , then we will first check if ‘ ‘ value for current node is or . And if its value is true then we will make it false. right Thread true false As now , there is no exist , it has its right child. right Thread (curr->key < el) { (curr->rightThread) { curr->right = ; curr->rightThread = ; } curr = curr->right; } // c++ // right subtree if if // if current node has rightThread == true NULL // make right child null of current node false // change value of rightThread for current node from true to false // go right subtree 4. Finally when we come out of position finding loop (for new node), if successor value does not remains ‘ ‘ (with which we initialize it) . we will store successor value as right child of new node and makes value of new node to . NULL right Thread true (successor) { newNode->right = successor; newNode->rightThread = ; } // c++ // adding thread if // if successor is not NULL // newNode stores data of new node // store successor value in right child of newNode true // makes rightThread valur of new Node to true This is my idea for insertion in Single Threaded Binary Tree , which I found easy. Thank you for reading it till the end 🙂 ! And If you are curious to see full implementation of Threaded Binary Tree , you may look at . this References you may find useful : Binary Search Tree Threaded Binary Tree
