# 1026. Maximum Difference Between Node and Ancestor

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: 
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

# Solution

Approach 1: recursion (or iteration with a stack), keeping the max and min seen in the subtrees.

# Code (Python)

Approach 1:

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        if not root or (not root.left and not root.right):
            return 0
        return self._find(root)[2]
    
    # can also define _find(self, node, min=node.val, max=node.val) and return a single max_diff
    def _find(self, node): # returns (min, max, max_diff)
        result = [node.val, node.val, 0]
        for child in (node.left, node.right):
            if not child:
                continue
            child_min, child_max, child_max_diff = self._find(child)
            result[0] = min(result[0], child_min)
            result[1] = max(result[1], child_max)
            result[2] = max(result[2], child_max_diff, abs(node.val - child_min), abs(node.val - child_max))
        return result
            

# Code (C++)

Approach 1:

Approach 2: