Maximum Difference Between Node and Ancestor

Share

Find maximum value |a-b| where a is an ancestor of b in a binary tree.

Example 1
Input: root=[8,3,10,1,6,null,14,null,null,4,7,13] → Output: 7
Example 2
Input: root=[1,null,2,null,0,3] → Output: 3

Solution Approach

DFS passing min and max of current path. At leaf, compute |max - min|.

  • DFS with current min and max along the path
  • At each node: update min and max
  • At null: return max - min (this is max |ancestor - node| for this path)
  • Return max of left and right results
Java
public int maxAncestorDiff(TreeNode root) {
    return dfs(root, root.val, root.val);
}
private int dfs(TreeNode node, int min, int max) {
    if (node == null) return max - min;
    min = Math.min(min, node.val);
    max = Math.max(max, node.val);
    return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
}
  • Time Complexity: O(n)
  • Space Complexity: O(h)