Inorder Non | A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Function to print inorder traversal using parent pointer ; Start traversal from root ; If left child is not traversed , find the leftmost child ; Print root 's data ; Mark left as done ; If right child exists ; If right child doesn 't exist, move to parent ; If this node is right child of its parent , visit parent 's parent first ; Driver Code
class newNode : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . key = item NEW_LINE self . parent = self . left = self . right = None NEW_LINE DEDENT DEDENT def insert ( node , key ) : NEW_LINE INDENT if node == None : NEW_LINE INDENT return newNode ( key ) NEW_LINE DEDENT if key < node . key : NEW_LINE INDENT node . left = insert ( node . left , key ) NEW_LINE node . left . parent = node NEW_LINE DEDENT elif key > node . key : NEW_LINE INDENT node . right = insert ( node . right , key ) NEW_LINE node . right . parent = node NEW_LINE DEDENT return node NEW_LINE DEDENT def inorder ( root ) : NEW_LINE INDENT leftdone = False NEW_LINE while root : NEW_LINE INDENT if leftdone == False : NEW_LINE INDENT while root . left : NEW_LINE INDENT root = root . left NEW_LINE DEDENT DEDENT print ( root . key , end = " ▁ " ) NEW_LINE leftdone = True NEW_LINE if root . right : NEW_LINE INDENT leftdone = False NEW_LINE root = root . right NEW_LINE DEDENT elif root . parent : NEW_LINE INDENT while root . parent and root == root . parent . right : NEW_LINE INDENT root = root . parent NEW_LINE DEDENT if root . parent == None : NEW_LINE INDENT break NEW_LINE DEDENT root = root . parent NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 24 ) NEW_LINE root = insert ( root , 27 ) NEW_LINE root = insert ( root , 29 ) NEW_LINE root = insert ( root , 34 ) NEW_LINE root = insert ( root , 14 ) NEW_LINE root = insert ( root , 4 ) NEW_LINE root = insert ( root , 10 ) NEW_LINE root = insert ( root , 22 ) NEW_LINE root = insert ( root , 13 ) NEW_LINE root = insert ( root , 3 ) NEW_LINE root = insert ( root , 2 ) NEW_LINE root = insert ( root , 6 ) NEW_LINE print ( " Inorder ▁ traversal ▁ is ▁ " ) NEW_LINE inorder ( root ) NEW_LINE DEDENT