Inorder predecessor and successor for a given key in BST | Iterative Approach | Function that finds predecessor and successor of key in BST . ; Search for given key in BST . ; If root is given key . ; the minimum value in right subtree is predecessor . ; the maximum value in left subtree is successor . ; If key is greater than root , then key lies in right subtree . Root could be predecessor if left subtree of key is null . ; If key is smaller than root , then key lies in left subtree . Root could be successor if right subtree of key is null . ; A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; Driver Code ; Key to be searched in BST ; Let us create following BST 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80
def findPreSuc ( root , pre , suc , key ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return NEW_LINE DEDENT while root != None : NEW_LINE INDENT if root . key == key : NEW_LINE INDENT if root . right : NEW_LINE INDENT suc [ 0 ] = root . right NEW_LINE while suc [ 0 ] . left : NEW_LINE INDENT suc [ 0 ] = suc [ 0 ] . left NEW_LINE DEDENT DEDENT if root . left : NEW_LINE INDENT pre [ 0 ] = root . left NEW_LINE while pre [ 0 ] . right : NEW_LINE INDENT pre [ 0 ] = pre [ 0 ] . right NEW_LINE DEDENT DEDENT return NEW_LINE DEDENT elif root . key < key : NEW_LINE INDENT pre [ 0 ] = root NEW_LINE root = root . right NEW_LINE DEDENT else : NEW_LINE INDENT suc [ 0 ] = root NEW_LINE root = root . left NEW_LINE DEDENT DEDENT DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . key = data NEW_LINE self . left = None NEW_LINE 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 DEDENT else : NEW_LINE INDENT node . right = insert ( node . right , key ) NEW_LINE DEDENT return node NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT key = 65 NEW_LINE 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 pre , suc = [ None ] , [ None ] NEW_LINE findPreSuc ( root , pre , suc , key ) NEW_LINE if pre [ 0 ] != None : NEW_LINE INDENT print ( " Predecessor ▁ is " , pre [ 0 ] . key ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT if suc [ 0 ] != None : NEW_LINE INDENT print ( " Successor ▁ is " , suc [ 0 ] . key ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT DEDENT