Given a Binary Tree, you need to find the maximum value which you can get by subtracting the value of node B from the value of node A, where A and B are two nodes of the binary tree and A is an ancestor of B. 
Example 1:
Input:
    5
 /    \
2      1
Output: 4
Explanation:The maximum difference we can
get is 4, which is bewteen 5 and 1.
Example 2:
Input:
      1
    /    \
   2      3
           \
            7
Output: -1
Explanation:The maximum difference we can
get is -1, which is between 1 and 2.
Your Task:
The task is to complete the function maxDiff() which finds the maximum difference between the node and its ancestor.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Note: H is the height of the tree.
Constraints:
2 <= Number of edges <= 10^{4}
0 <= Data of a node <= 10^{5}
Note: The Input/Output format and Examples given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from the stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



#Function to return the maximum difference between any node and its ancestor.

def maxDiff(root):

   

    # code here





Solutions:
import math

def diff(root, res):
	if root is None:
		return (math.inf, res)
	if not root.left and (not root.right):
		return (root.data, res)
	(min_left, res) = diff(root.left, res)
	(min_right, res) = diff(root.right, res)
	min_node = min(min_left, min_right)
	res = max(res, root.data - min_node)
	return (min(min_node, root.data), res)

def maxDiff(root):
	res = -math.inf
	(_, res) = diff(root, res)
	return res