https://leetcode.com/problems/maximum-difference-between-node-and-ancestor

Let us traverse our tree from top to bottom with dfs function, where we pass parameters:

  1. node is current node we visiting
  2. high is maximum over all node values, which are above our node, that is the maximum among parent, parent of parent, parent of parent of parent and so on.
  3. low is minumum over all node values, which are above our node.

No, we iterate over our tree and:

  1. Update our self.Max: look at two values abs(node.val - low) and abs(node.val - high): it will be the biggest candidates for difference between node and its ancestor, where node is lying in lower layer.
  2. Now, we run our dfs for left and right children, where we updated low and high values: we need to include current node.val.

We start with dfs(root, root.val, root.val), because we do not have nodes which are above our root.

Complexity: time complexity is O(n), space complexity is O(h), as any usual dfs have.

class Solution:
    def maxAncestorDiff(self, root):
        
        self.Max = 0
        def dfs(node, low, high):    
            if not node: return

            self.Max = max(self.Max, abs(node.val-low), abs(node.val-high))
            low1, high1 = min(low, node.val), max(high, node.val)
            dfs(node.left, low1, high1)
            dfs(node.right, low1, high1)
                
        dfs(root, root.val, root.val)
        return self.Max

If you like the solution, you can upvote it on leetcode discussion section: Problem 1026