Maximum Difference Between Node and Ancestor

medium binary tree dfs

Problem

Given the root of a binary tree, find the maximum value of |a.val - b.val| over all ancestor-descendant pairs (a, b). Equivalently, on each root-to-leaf path, compute (path max - path min) and return the largest such value.

Inputroot = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]

Output7

|8 - 1| = 7 along path 8 → 3 → 1.

tree (level order, use 'null' for missing)

def max_ancestor_diff(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)

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);
}

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    private 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));
    }
}

int dfs(TreeNode* node, int mn, int mx) {
    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));
}
int maxAncestorDiff(TreeNode* root) {
    return dfs(root, root->val, root->val);
}

Explanation

For any ancestor-descendant pair, the biggest possible difference on a path comes from its largest value minus its smallest value. So instead of checking every pair, we just track the min and max as we travel down each path.

The DFS carries two running values down the recursion: mn and mx, the smallest and largest node values seen so far on the path from the root.

At each node we widen the window with mn = min(mn, node.val) and mx = max(mx, node.val), then keep descending into both children. When we hit a null child, the path is complete and we return mx - mn — the spread along that path.

Each node takes the larger answer from its two sides, so the value that bubbles up to the root is the maximum spread over all root-to-leaf paths.

Example: in [8, 3, 10, 1, 6, ...] the path 8 → 3 → 1 has max 8 and min 1, giving 8 - 1 = 7, which is the answer.

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