maximum difference between node and ancestor


Credit: lostworld21

 1 class Solution:
 2     def maxAncestorDiff(self, root):
 3         def dfs(self, n, mn, mx):
 4             if not n:
 5                 return 0
 6             new_mn = min(n.val, mn)
 7             new_mx = max(n.val, mx)
 8             return max(
 9                 max(abs(n.val - mn), abs(n.val - mx)),
10                 dfs(n.left, new_mn, new_mx),
11                 dfs(n.right, new_mn, new_mx),
12             )
14     return dfs(root, root.val, root.val)

The mistake i made on this problem was to take a bottom up approach rather than a top down approach.

The bottom up approach was too complex, as you're basically uncertain whether you have a left child, a right child, both, or neither.

Making queries like node.left.val is totally impossible and it was a huge mistake even trying to do such a thing.

In this implementation (above) the base case gracefully handles children not existing, and the top down approach leads to very clean code.