# 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.)
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.
The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.
Approach 1: recursion (or iteration with a stack), keeping the max and min seen in the subtrees.
# Code (Python)
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) # 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 = min(result, child_min) result = max(result, child_max) result = max(result, child_max_diff, abs(node.val - child_min), abs(node.val - child_max)) return result
# Code (C++)