Maximum difference between node and its ancestor in Binary Tree | Python3 program to find maximum difference between node and its ancestor ; Helper function that allocates a new node with the given data and None left and right poers . ; Recursive function to calculate maximum ancestor - node difference in binary tree . It updates value at ' res ' to store the result . The returned value of this function is minimum value in subtree rooted with ' t ' ; Returning Maximum value if node is not there ( one child case ) ; If leaf node then just return node 's value  ; Recursively calling left and right subtree for minimum value ; Updating res if ( node value - minimum value from subtree ) is bigger than res ; Returning minimum value got so far ; This function mainly calls maxDiffUtil ( ) ; Initialising result with minimum value ; Helper function to print inorder traversal of binary tree ; Driver Code ; Let us create Binary Tree shown in above example
_MIN = - 2147483648 NEW_LINE _MAX = 2147483648 NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def maxDiffUtil ( t , res ) : NEW_LINE INDENT if ( t == None ) : NEW_LINE INDENT return _MAX , res NEW_LINE DEDENT if ( t . left == None and t . right == None ) : NEW_LINE INDENT return t . key , res NEW_LINE DEDENT a , res = maxDiffUtil ( t . left , res ) NEW_LINE b , res = maxDiffUtil ( t . right , res ) NEW_LINE val = min ( a , b ) NEW_LINE res = max ( res , t . key - val ) NEW_LINE return min ( val , t . key ) , res NEW_LINE DEDENT def maxDiff ( root ) : NEW_LINE INDENT res = _MIN NEW_LINE x , res = maxDiffUtil ( root , res ) NEW_LINE return res NEW_LINE DEDENT def inorder ( root ) : NEW_LINE INDENT if ( root ) : NEW_LINE INDENT inorder ( root . left ) NEW_LINE prf ( " % d ▁ " , root . key ) NEW_LINE inorder ( root . right ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 8 ) NEW_LINE root . left = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . left . right = newNode ( 6 ) NEW_LINE root . left . right . left = newNode ( 4 ) NEW_LINE root . left . right . right = newNode ( 7 ) NEW_LINE root . right = newNode ( 10 ) NEW_LINE root . right . right = newNode ( 14 ) NEW_LINE root . right . right . left = newNode ( 13 ) NEW_LINE print ( " Maximum ▁ difference ▁ between ▁ a ▁ node ▁ and " , " its ▁ ancestor ▁ is ▁ : " , maxDiff ( root ) ) NEW_LINE DEDENT