Maximum Difference Between Node And Ancestor - Leetcode Solution

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.

Approach:

One way to solve this problem is to perform a DFS (Depth First Search) on the binary tree. During the DFS, we maintain the minimum and maximum values we have seen so far on the path from the root to the current node. Then, for each node, we calculate the maximum difference between the current node's value and the minimum and maximum values we have seen so far. We take the maximum of these differences and return it as the result.

Algorithm:

1. Initialize a variable maxDiff to 0.
2. Define a recursive function maxDiffHelper(node, minVal, maxVal) that takes a binary tree node, a minimum value so far, and a maximum value so far as inputs. This function performs a DFS on the binary tree and returns the maximum difference between node and its ancestors.
3. If node is None, return 0.
4. Calculate the difference between the current node's value and the minimum value so far and assign it to a variable left.
5. Calculate the difference between the current node's value and the maximum value so far and assign it to a variable right.
6. Update the value of maxDiff to be the maximum of maxDiff, left, and right.
7. Recursively call maxDiffHelper(node.left, min(minVal, node.val), max(maxVal, node.val)).
8. Recursively call maxDiffHelper(node.right, min(minVal, node.val), max(maxVal, node.val)).
9. Return maxDiff.

Python Code:

class Solution: def maxAncestorDiff(self, root: TreeNode) -> int: def maxDiffHelper(node, minVal, maxVal): if not node: return 0 left = abs(node.val - minVal) right = abs(node.val - maxVal) maxDiff = max(left, right, maxDiffHelper(node.left, min(minVal, node.val), max(maxVal, node.val)), maxDiffHelper(node.right, min(minVal, node.val), max(maxVal, node.val))) return maxDiff

    maxDiff = maxDiffHelper(root, root.val, root.val)
    return maxDiff

Time Complexity:

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. This is because we perform a DFS on each node exactly once. The space complexity of this solution is O(H), where H is the height of the binary tree. This is because the recursion stack can have at most H nodes.

1