# 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: