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 Code
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . info = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE self . lthread = True NEW_LINE self . rthread = True NEW_LINE DEDENT DEDENT def insert ( root , ikey ) : NEW_LINE INDENT ptr = root NEW_LINE par = None NEW_LINE while ptr != None : NEW_LINE INDENT if ikey == ( ptr . info ) : NEW_LINE INDENT print ( " Duplicate ▁ Key ▁ ! " ) NEW_LINE return root NEW_LINE DEDENT par = ptr NEW_LINE if ikey < ptr . info : NEW_LINE INDENT if ptr . lthread == False : NEW_LINE INDENT ptr = ptr . left NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ptr . rthread == False : NEW_LINE INDENT ptr = ptr . right NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT tmp = newNode ( ikey ) NEW_LINE if par == None : NEW_LINE INDENT root = tmp NEW_LINE tmp . left = None NEW_LINE tmp . right = None NEW_LINE DEDENT elif ikey < ( par . info ) : NEW_LINE INDENT tmp . left = par . left NEW_LINE tmp . right = par NEW_LINE par . lthread = False NEW_LINE par . left = tmp NEW_LINE DEDENT else : NEW_LINE INDENT tmp . left = par NEW_LINE tmp . right = par . right NEW_LINE par . rthread = False NEW_LINE par . right = tmp NEW_LINE DEDENT return root NEW_LINE DEDENT def inorderSuccessor ( ptr ) : NEW_LINE INDENT if ptr . rthread == True : NEW_LINE INDENT return ptr . right NEW_LINE DEDENT ptr = ptr . right NEW_LINE while ptr . lthread == False : NEW_LINE INDENT ptr = ptr . left NEW_LINE DEDENT return ptr NEW_LINE DEDENT def inorder ( root ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT print ( " Tree ▁ is ▁ empty " ) NEW_LINE DEDENT ptr = root NEW_LINE while ptr . lthread == False : NEW_LINE INDENT ptr = ptr . left NEW_LINE DEDENT while ptr != None : NEW_LINE INDENT print ( ptr . info , end = " ▁ " ) NEW_LINE ptr = inorderSuccessor ( ptr ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 20 ) NEW_LINE root = insert ( root , 10 ) NEW_LINE root = insert ( root , 30 ) NEW_LINE root = insert ( root , 5 ) NEW_LINE root = insert ( root , 16 ) NEW_LINE root = insert ( root , 14 ) NEW_LINE root = insert ( root , 17 ) NEW_LINE root = insert ( root , 13 ) NEW_LINE inorder ( root ) NEW_LINE DEDENT