Inorder predecessor and successor for a given key in BST | A Binary Tree Node Utility function to create a new tree node ; since inorder traversal results in ascendingorder visit to node , we can store the values of the largest o which is smaller than a ( predecessor ) and smallest no which is large than a ( successor ) using inorder traversal ; If root is None return ; traverse the left subtree ; root data is greater than a ; q stores the node whose data is greater than a and is smaller than the previously stored data in * q which is successor ; if the root data is smaller than store it in p which is predecessor ; traverse the right subtree ; Driver Code
class getnode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def find_p_s ( root , a , p , q ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return NEW_LINE DEDENT find_p_s ( root . left , a , p , q ) NEW_LINE if ( root and root . data > a ) : NEW_LINE INDENT if ( ( not q [ 0 ] ) or q [ 0 ] and q [ 0 ] . data > root . data ) : NEW_LINE INDENT q [ 0 ] = root NEW_LINE DEDENT DEDENT elif ( root and root . data < a ) : NEW_LINE INDENT p [ 0 ] = root NEW_LINE DEDENT find_p_s ( root . right , a , p , q ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = getnode ( 50 ) NEW_LINE root1 . left = getnode ( 20 ) NEW_LINE root1 . right = getnode ( 60 ) NEW_LINE root1 . left . left = getnode ( 10 ) NEW_LINE root1 . left . right = getnode ( 30 ) NEW_LINE root1 . right . left = getnode ( 55 ) NEW_LINE root1 . right . right = getnode ( 70 ) NEW_LINE p = [ None ] NEW_LINE q = [ None ] NEW_LINE find_p_s ( root1 , 55 , p , q ) NEW_LINE if ( p [ 0 ] ) : NEW_LINE INDENT print ( p [ 0 ] . data , end = " " ) NEW_LINE DEDENT if ( q [ 0 ] ) : NEW_LINE INDENT print ( " " , q [ 0 ] . data ) NEW_LINE DEDENT DEDENT