Maximum Difference Between Node and Ancestor

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: A is an ancestor of B or if the given B is an ancestor of A.

**Example TreeNode root =

Example

Here's an example solution for LeetCode problem 1026, "Maximum Difference Between Node and Ancestor":

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 there exists a path from A to B (including A and B themselves).

Example

For example, consider the following binary tree:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

The maximum difference between a node and its ancestor in this tree is 7, which occurs between node 1 and node 8 (or node 10).

Solutions

Approach: Depth-First Search (DFS)

To solve this problem, we can use a depth-first search (DFS) approach to track the minimum and maximum values encountered on the path from the root to each node. Here's how the solution can be implemented in Java, Python, and C++:

Java

class Solution {
    int maxDifference = 0;
    
    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return maxDifference;
    }
    
    private void dfs(TreeNode node, int minAncestor, int maxAncestor) {
        if (node == null) return;
        
        int currentDiff = Math.max(Math.abs(node.val - minAncestor), Math.abs(node.val - maxAncestor));
        maxDifference = Math.max(maxDifference, currentDiff);
        
        minAncestor = Math.min(minAncestor, node.val);
        maxAncestor = Math.max(maxAncestor, node.val);
        
        dfs(node.left, minAncestor, maxAncestor);
        dfs(node.right, minAncestor, maxAncestor);
    }
}

Python

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_diff = 0
        
        def dfs(node, min_ancestor, max_ancestor):
            if not node:
                return
            
            current_diff = max(abs(node.val - min_ancestor), abs(node.val - max_ancestor))
            self.max_diff = max(self.max_diff, current_diff)
            
            min_ancestor = min(min_ancestor, node.val)
            max_ancestor = max(max_ancestor, node.val)
            
            dfs(node.left, min_ancestor, max_ancestor)
            dfs(node.right, min_ancestor, max_ancestor)
        
        dfs(root, root.val, root.val)
        return self.max_diff

C++

class Solution {
public:
    int maxDifference = 0;
    
    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return maxDifference;
    }
    
    void dfs(TreeNode* node, int minAncestor, int maxAncestor) {
        if (!node) return;
        
        int currentDiff = max(abs(node->val - minAncestor), abs(node->val - maxAncestor));
        maxDifference = max(maxDifference, currentDiff);
        
        minAncestor = min(minAncestor, node->val);
        maxAncestor = max(maxAncestor, node->val);
        
        dfs(node->left, minAncestor, maxAncestor);
        dfs(node->right, minAncestor, maxAncestor);
    }
};