Problem 1026

(Last updated: )

Question 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.

Solution

I opted for a brute force approach, which ultimately got accepted (with poor run time). There are certainly more optimal approaches available. I will refactor this code, or add a new section to this post in the future if time permits

Main idea:

Starting at the root node, perform dfs to find the node such that $\texttt{v = |root.val - node.val|}$ is maximized. Record this ancestor-child value in the array $\texttt{pair}$ (initialized with [root.val, root.val] whose second coordinate is updated with node.val for a node that produces a bigger $\texttt{v}$) and record the maximal $\texttt{v}$ in a separate array $\texttt{arr}$. Repeat this process for the left and right sub-trees, appending to arr the maximum of the current maximal $\texttt{v}$ and arr[-1]. Once the tree is fully traversed, return arr[-1].

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def dfs(self, root, pair):
    max_diff = abs(pair[1]-pair[0])
    if root == None:
        return
    v = abs(pair[0] - root.val)
    if(v >= max_diff):
        pair[1] = root.val
    
    self.dfs(root.left, pair)
    self.dfs(root.right, pair)

    return abs(pair[1]-pair[0])

def helper(self, root, arr):
    arr.append(max(arr[-1], self.dfs(root, [root.val,root.val])))
    if(root.left != None):
        self.helper(root.left, arr)
    if(root.right!= None):
        self.helper(root.right, arr)
    return arr[-1]

def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
    return self.helper(root, [0])

Comments:

Time complexity: O(nlog n) (b/c we are doing a log(n) dfs for each node).

At the time of submission, the above solution passes leetcode submission cases in 2916ms, beats 5.03% of users. It uses 19.41MB of memory, beating 65.44% of users.

One bit of time-optimization we can do is to do one dfs and build an array of ancestor-successor while keeping track of the optimal pair. This would run in O(n) since we have to hit every node, but we only do one dfs.