[Problem] Maximum Difference Between Node and Ancestor

Problem Link

Problem Statement

Given the root of a binary tree, find the maximum value v for which there exist 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.

Approach

Using depth-first search allows us to go check all the nodes only once. Since the problem only requires to find the maximum difference, we do not have to go through all ancestors of a given node, but only the maximum and minimum.

To achieve this, I defined a helper function that continues to keep track of the previous maximum and minimum. One thing I forgot to utilize is to use a global variable using self.variable_name, which I will continue to use in the next following problems.

Solution

class Solution(object):
    def maxAncestorDiff(self, root):
        max_dif = 0
        max_val = root.val
        min_val = root.val

        def search(node, max_val, min_val): 
            if node == None:
                return
            max_dif = max(abs(max_val - node.val), abs(min_val - node.val))
            max_val = max(max_val, node.val)
            min_val = min(min_val, node.val)
            max_dif2 = max(search(node.left, max_val, min_val), search(node.right, max_val, min_val))
            
            return max(max_dif, max_dif2)