Binary Search Tree insert with Parent Pointer | A utility function to create a new BST Node ; A utility function to do inorder traversal of BST ; 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 ; Set parent of root of left subtree ; Set parent of root of right subtree ; return the ( unchanged ) Node pointer ; Driver Code ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 ; print iNoder traversal of the BST
class newNode : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . key = item NEW_LINE self . left = self . right = None NEW_LINE self . parent = None NEW_LINE DEDENT DEDENT def inorder ( root ) : NEW_LINE INDENT if root != None : NEW_LINE INDENT inorder ( root . left ) NEW_LINE print ( " Node ▁ : " , root . key , " , ▁ " , end = " " ) NEW_LINE if root . parent == None : NEW_LINE INDENT print ( " Parent ▁ : ▁ NULL " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Parent ▁ : ▁ " , root . parent . key ) NEW_LINE DEDENT inorder ( root . right ) 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 lchild = insert ( node . left , key ) NEW_LINE node . left = lchild NEW_LINE lchild . parent = node NEW_LINE DEDENT elif key > node . key : NEW_LINE INDENT rchild = insert ( node . right , key ) NEW_LINE node . right = rchild NEW_LINE rchild . parent = node NEW_LINE DEDENT return node NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 50 ) NEW_LINE insert ( root , 30 ) NEW_LINE insert ( root , 20 ) NEW_LINE insert ( root , 40 ) NEW_LINE insert ( root , 70 ) NEW_LINE insert ( root , 60 ) NEW_LINE insert ( root , 80 ) NEW_LINE inorder ( root ) NEW_LINE DEDENT