insertion in threaded binary tree
snippet in c

insertion in threaded binary tree

user902

// Insertion in Binary Threaded Tree 
struct Node
{
  struct Node *left, *right;
  int info;
  boolean lthread; 
  boolean rthread; 
};

/*
Case 1: Insertion in empty tree
Both left and right pointers of tmp will be set to NULL and new node becomes the root.
*/ 
root = tmp;
tmp -> left = NULL;
tmp -> right = NULL;

/*
Case 2: When new node inserted as the left child
After inserting the node at its proper place we have to make its left and right threads points to inorder predecessor and successor respectively. The node which was inorder successor. So the left and right threads of the new node will be-
*/

tmp -> left = par ->left; // par is the parent node
tmp -> right = par;

/*
Before insertion, the left pointer of parent was a thread, but after insertion it will be a link pointing to the new node.
*/
par -> lthread = false;
par -> left = temp;

/*
Case 3: When new node is inserted as the right child
The parent of tmp is its inorder predecessor. The node which was inorder successor of the parent is now the inorder successor of this node tmp. So the left and right threads of the new node will be-
*/ 
tmp -> left = par;
tmp -> right = par -> right;

/*
Before insertion, the right pointer of parent was a thread, but after insertion it will be a link pointing to the new node.
*/

par -> rthread = false;
par -> right = tmp;

insertion in threaded binary tree

user3730

// Implementation of Insertion in Threaded Binary Search Tree. 
#include<bits/stdc++.h> 
using namespace std; 
  
struct Node 
{ 
    struct Node *left, *right; 
    int info; 
  
    // True if left pointer points to predecessor 
    // in Inorder Traversal 
    bool lthread; 
  
    // True if right pointer points to predecessor 
    // in Inorder Traversal 
    bool rthread; 
}; 
  
// Insert a Node in Binary Threaded Tree 
struct Node *insert(struct Node *root, int ikey) 
{ 
    // Searching for a Node with given value 
    Node *ptr = root; 
    Node *par = NULL; // Parent of key to be inserted 
    while (ptr != NULL) 
    { 
        // If key already exists, return 
        if (ikey == (ptr->info)) 
        { 
            printf("Duplicate Key !\n"); 
            return root; 
        } 
  
        par = ptr; // Update parent pointer 
  
        // Moving on left subtree. 
        if (ikey < ptr->info) 
        { 
            if (ptr -> lthread == false) 
                ptr = ptr -> left; 
            else
                break; 
        } 
  
        // Moving on right subtree. 
        else
        { 
            if (ptr->rthread == false) 
                ptr = ptr -> right; 
            else
                break; 
        } 
    } 
  
    // Create a new node 
    Node *tmp = new Node; 
    tmp -> info = ikey; 
    tmp -> lthread = true; 
    tmp -> rthread = true; 
  
    if (par == NULL) 
    { 
        root = tmp; 
        tmp -> left = NULL; 
        tmp -> right = NULL; 
    } 
    else if (ikey < (par -> info)) 
    { 
        tmp -> left = par -> left; 
        tmp -> right = par; 
        par -> lthread = false; 
        par -> left = tmp; 
    } 
    else
    { 
        tmp -> left = par; 
        tmp -> right = par -> right; 
        par -> rthread = false; 
        par -> right = tmp; 
    } 
  
    return root; 
} 
  
// Returns inorder successor using rthread 
struct Node *inorderSuccessor(struct Node *ptr) 
{ 
    // If rthread is set, we can quickly find 
    if (ptr -> rthread == true) 
        return ptr->right; 
  
    // Else return leftmost child of right subtree 
    ptr = ptr -> right; 
    while (ptr -> lthread == false) 
        ptr = ptr -> left; 
    return ptr; 
} 
  
// Printing the threaded tree 
void inorder(struct Node *root) 
{ 
    if (root == NULL) 
        printf("Tree is empty"); 
  
    // Reach leftmost node 
    struct Node *ptr = root; 
    while (ptr -> lthread == false) 
        ptr = ptr -> left; 
  
    // One by one print successors 
    while (ptr != NULL) 
    { 
        printf("%d ",ptr -> info); 
        ptr = inorderSuccessor(ptr); 
    } 
} 
  
// Driver Program 
int main() 
{ 
    struct Node *root = NULL; 
  
    root = insert(root, 20); 
    root = insert(root, 10); 
    root = insert(root, 30); 
    root = insert(root, 5); 
    root = insert(root, 16); 
    root = insert(root, 14); 
    root = insert(root, 17); 
    root = insert(root, 13); 
  
    inorder(root); 
  
    return 0; 
}