Maximum Difference Between Node and Ancestor

Problem

Return the maximum value |node.val - ancestor.val| for any ancestor-descendant pair.

Key insight: DFS tracking current path min and max. At each node, the max diff = max(|val-min|, |val-max|) along path.

Solutions

// C++
int maxAncestorDiff(TreeNode* root) {
    function<int(TreeNode*, int, int)> dfs = [&](TreeNode* node, int mn, int mx) -> int {
        if (!node) return mx - mn;
        mn = min(mn, node->val);
        mx = max(mx, node->val);
        return max(dfs(node->left, mn, mx), dfs(node->right, mn, mx));
    };
    return dfs(root, root->val, root->val);
}

// Java
public int maxAncestorDiff(TreeNode root) {
    return dfs(root, root.val, root.val);
}
int dfs(TreeNode node, int mn, int mx) {
    if (node == null) return mx - mn;
    mn = Math.min(mn, node.val);
    mx = Math.max(mx, node.val);
    return Math.max(dfs(node.left, mn, mx), dfs(node.right, mn, mx));
}

// JavaScript
function maxAncestorDiff(root) {
    function dfs(node, mn, mx) {
        if (!node) return mx - mn;
        mn = Math.min(mn, node.val);
        mx = Math.max(mx, node.val);
        return Math.max(dfs(node.left, mn, mx), dfs(node.right, mn, mx));
    }
    return dfs(root, root.val, root.val);
}

# Python
def maxAncestorDiff(root):
    def dfs(node, mn, mx):
        if not node:
            return mx - mn
        mn = min(mn, node.val)
        mx = max(mx, node.val)
        return max(dfs(node.left, mn, mx), dfs(node.right, mn, mx))
    return dfs(root, root.val, root.val)

Complexity

Time: O(n)
Space: O(h)