Inorder Successor in Binary Search Tree | A binary tree node ; Given a binary search tree and a number , inserts a new node with the given number in the correct place in the tree . Returns the new root pointer which the caller should then use ( the standard trick to avoidusing reference parameters ) ; 1 ) If tree is empty then return a new singly node ; 2 ) Otherwise , recur down the tree ; return the unchanged node pointer ; Step 1 of the above algorithm ; Step 2 of the above algorithm ; Given a non - empty binary search tree , return the minimum data value found in that tree . Note that the entire tree doesn 't need to be searched ; loop down to find the leftmost leaf ; Driver progam to test above function
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def insert ( node , data ) : NEW_LINE INDENT if node is None : NEW_LINE INDENT return Node ( data ) NEW_LINE DEDENT else : NEW_LINE INDENT if data <= node . data : NEW_LINE INDENT temp = insert ( node . left , data ) NEW_LINE node . left = temp NEW_LINE temp . parent = node NEW_LINE DEDENT else : NEW_LINE INDENT temp = insert ( node . right , data ) NEW_LINE node . right = temp NEW_LINE temp . parent = node NEW_LINE DEDENT return node NEW_LINE DEDENT DEDENT def inOrderSuccessor ( n ) : NEW_LINE INDENT if n . right is not None : NEW_LINE INDENT return minValue ( n . right ) NEW_LINE DEDENT p = n . parent NEW_LINE while ( p is not None ) : NEW_LINE INDENT if n != p . right : NEW_LINE INDENT break NEW_LINE DEDENT n = p NEW_LINE p = p . parent NEW_LINE DEDENT return p NEW_LINE DEDENT def minValue ( node ) : NEW_LINE INDENT current = node NEW_LINE while ( current is not None ) : NEW_LINE INDENT if current . left is None : NEW_LINE INDENT break NEW_LINE DEDENT current = current . left NEW_LINE DEDENT return current NEW_LINE DEDENT root = None NEW_LINE root = insert ( root , 20 ) NEW_LINE root = insert ( root , 8 ) ; NEW_LINE root = insert ( root , 22 ) ; NEW_LINE root = insert ( root , 4 ) ; NEW_LINE root = insert ( root , 12 ) ; NEW_LINE root = insert ( root , 10 ) ; NEW_LINE root = insert ( root , 14 ) ; NEW_LINE temp = root . left . right . right NEW_LINE succ = inOrderSuccessor ( root , temp ) NEW_LINE if succ is not None : NEW_LINE INDENT print " \n Inorder ▁ Successor ▁ of ▁ % ▁ d ▁ is ▁ % ▁ d ▁ " % ( temp . data , succ . data ) NEW_LINE DEDENT else : NEW_LINE INDENT print " \n Inorder ▁ Successor ▁ doesn ' t ▁ exist " NEW_LINE DEDENT