// Insertion in Threaded Binary Search Tree. #include   using namespace std; struct Node {  struct Node *left *right;  int info;  // False if left pointer points to predecessor  // in Inorder Traversal  bool lthread;  // False if right pointer points to successor  // 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; } 

// Java program Insertion in Threaded Binary Search Tree.  import java.util.*; public class solution { static class Node  {   Node left right;   int info;     // False if left pointer points to predecessor   // in Inorder Traversal   boolean lthread;     // False if right pointer points to successor   // in Inorder Traversal   boolean rthread;  };    // Insert a Node in Binary Threaded Tree  static Node insert( 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))   {   System.out.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  static Node inorderSuccessor( 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  static void inorder( Node root)  {   if (root == null)   System.out.printf('Tree is empty');     // Reach leftmost node   Node ptr = root;   while (ptr . lthread == false)   ptr = ptr . left;     // One by one print successors   while (ptr != null)   {   System.out.printf('%d 'ptr . info);   ptr = inorderSuccessor(ptr);   }  }    // Driver Program  public static void main(String[] args) {   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);  }  } //contributed by Arnab Kundu // This code is updated By Susobhan Akhuli 

# Insertion in Threaded Binary Search Tree.  class newNode: def __init__(self key): # False if left pointer points to  # predecessor in Inorder Traversal  self.info = key self.left = None self.right =None self.lthread = True # False if right pointer points to  # successor in Inorder Traversal  self.rthread = True # Insert a Node in Binary Threaded Tree  def insert(root ikey): # Searching for a Node with given value  ptr = root par = None # Parent of key to be inserted  while ptr != None: # If key already exists return  if ikey == (ptr.info): print('Duplicate Key !') 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  tmp = newNode(ikey) if par == None: root = tmp tmp.left = None tmp.right = None elif 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  def inorderSuccessor(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  def inorder(root): if root == None: print('Tree is empty') # Reach leftmost node  ptr = root while ptr.lthread == False: ptr = ptr.left # One by one print successors  while ptr != None: print(ptr.infoend=' ') ptr = inorderSuccessor(ptr) # Driver Code if __name__ == '__main__': root = None 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) # This code is contributed by PranchalK 

using System; // C# program Insertion in Threaded Binary Search Tree.  public class solution { public class Node {  public Node left right;  public int info;  // False if left pointer points to predecessor   // in Inorder Traversal   public bool lthread;  // False if right pointer points to successor   // in Inorder Traversal   public bool rthread; } // Insert a Node in Binary Threaded Tree  public static Node insert(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))  {  Console.Write('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  public static Node inorderSuccessor(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  public static void inorder(Node root) {  if (root == null)  {  Console.Write('Tree is empty');  }  // Reach leftmost node   Node ptr = root;  while (ptr.lthread == false)  {  ptr = ptr.left;  }  // One by one print successors   while (ptr != null)  {  Console.Write('{0:D} 'ptr.info);  ptr = inorderSuccessor(ptr);  } } // Driver Program  public static void Main(string[] args) {  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); } }  // This code is contributed by Shrikant13 

<script> // javascript program Insertion in Threaded Binary Search Tree.   class Node {  constructor(){ this.left = null this.right = null;  this.info = 0;  // False if left pointer points to predecessor  // in Inorder Traversal  this.lthread = false;  // False if right pointer points to successor  // in Inorder Traversal  this.rthread = false;  }  }  // Insert a Node in Binary Threaded Tree  function insert(root  ikey) {  // Searching for a Node with given value var ptr = root; var par = null; // Parent of key to be inserted  while (ptr != null) {  // If key already exists return  if (ikey == (ptr.info)) {  document.write('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 var 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  function inorderSuccessor(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  function inorder(root) {  if (root == null)  document.write('Tree is empty');  // Reach leftmost node var ptr = root;  while (ptr.lthread == false)  ptr = ptr.left;  // One by one print successors  while (ptr != null) {  document.write(ptr.info+' ');  ptr = inorderSuccessor(ptr);  }  }  // Driver Program   var 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); // This code contributed by aashish1995 </script>