Problem statement

https://binarysearch.com/problems/Largest-Difference-Between-Node-and-a-Descendant/

Solution

Equal to Leetcode 1026. Maximum Difference Between Node and Ancestor.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(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)
        
        if not root: return 0
        dfs(root, root.val, root.val)
        return self.Max