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