Maximum Difference Between Node and Ancestor

Share

Given 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.

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: pass the current minimum and maximum values seen on the path from root to current node. At each leaf, the answer candidate is max - min.

  • dfs(node, minVal, maxVal):
  • If node==null: return maxVal - minVal.
  • Update minVal = min(minVal, node.val), maxVal = max(maxVal, node.val).
  • Return max(dfs(left, minVal, maxVal), dfs(right, minVal, maxVal)).
Java
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    private int dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        return Math.max(dfs(node.left, minVal, maxVal), dfs(node.right, minVal, maxVal));
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(H)