Inorder Successor of a node in Binary Tree | A Binary Tree Node Utility function to create a new tree node ; function to find left most node in a tree ; function to find right most node in a tree ; recursive function to find the Inorder Scuccessor when the right child of node x is None ; function to find inorder successor of a node ; Case1 : If right child is not None ; Case2 : If right child is None ; case3 : If x is the right most node ; Driver Code ; Case 1 ; case 2 ; case 3
class newNode : 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 leftMostNode ( node ) : NEW_LINE INDENT while ( node != None and node . left != None ) : NEW_LINE INDENT node = node . left NEW_LINE DEDENT return node NEW_LINE DEDENT def rightMostNode ( node ) : NEW_LINE INDENT while ( node != None and node . right != None ) : NEW_LINE INDENT node = node . right NEW_LINE DEDENT return node NEW_LINE DEDENT def findInorderRecursive ( root , x ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return None NEW_LINE DEDENT if ( root == x or ( findInorderRecursive ( root . left , x ) ) or ( findInorderRecursive ( root . right , x ) ) ) : NEW_LINE INDENT if findInorderRecursive ( root . right , x ) : NEW_LINE INDENT temp = findInorderRecursive ( root . right , x ) NEW_LINE DEDENT else : NEW_LINE INDENT temp = findInorderRecursive ( root . left , x ) NEW_LINE DEDENT if ( temp ) : NEW_LINE INDENT if ( root . left == temp ) : NEW_LINE INDENT print ( " Inorder ▁ Successor ▁ of " , x . data , end = " " ) NEW_LINE print ( " ▁ is " , root . data ) NEW_LINE return None NEW_LINE DEDENT DEDENT return root NEW_LINE DEDENT return None NEW_LINE DEDENT def inorderSuccesor ( root , x ) : NEW_LINE INDENT if ( x . right != None ) : NEW_LINE INDENT inorderSucc = leftMostNode ( x . right ) NEW_LINE print ( " Inorder ▁ Successor ▁ of " , x . data , " is " , end = " ▁ " ) NEW_LINE print ( inorderSucc . data ) NEW_LINE DEDENT if ( x . right == None ) : NEW_LINE INDENT f = 0 NEW_LINE rightMost = rightMostNode ( root ) NEW_LINE if ( rightMost == x ) : NEW_LINE INDENT print ( " No ▁ inorder ▁ successor ! " , " Right ▁ most ▁ node . " ) NEW_LINE DEDENT else : NEW_LINE INDENT findInorderRecursive ( root , x ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . right = newNode ( 6 ) NEW_LINE inorderSuccesor ( root , root . right ) NEW_LINE inorderSuccesor ( root , root . left . left ) NEW_LINE inorderSuccesor ( root , root . right . right ) NEW_LINE DEDENT