Node and Ancestor Max Diff

Problem Overview

You want the largest value of (ancestor.data - descendant.data) where the ancestor is above the descendant on the tree.

Intuition

You want the largest value of (ancestor.data - descendant.data) where the ancestor is above the descendant on the tree. For a fixed node, the best ancestor is the maximum value on the path from root to that node. Carry that max down in a pre-order DFS and update the answer at every non-root node.

Algorithm

1DFS(node, maxAnc): if node is null, return.
2If maxAnc is set, ans = max(ans, maxAnc - node.data).
3maxAnc = max(maxAnc, node.data).
4Recurse on left and right with the updated maxAnc.
5Start from root with no ancestor (sentinel) and return ans.

Example Walkthrough

Input: root = 8, left=3 (1,6 with 4,7), right=10 (14 with 13)

1. At node 1 the path max ancestor is 8, so 8-1=7.
2. Other pairs like 8-3=5 or 3-7=-4 are smaller.
3. Maximum ancestor minus descendant is 7.

Output: 7

Common Pitfalls

• GFG subtracts descendant from ancestor, not absolute difference - negative diffs are allowed but you take the max.
• The root has no ancestor, so skip updating ans there.
• Ancestor means any node on the path from root down, not only the parent.
• A single-node tree has no valid pair; handle if the platform allows it.

Node and Ancestor Max Diff.java

Java

// Approach: For ancestor - descendant, the best diff at a node uses the largest
// ancestor value on the path from root. Pre-order DFS carries that max down;
// at each node update ans with maxAncestor - node.data, then extend max.
// Complexity: O(n) time and O(h) space (h = tree height).

class Node {

    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {

    int maxDiff(Node root) {
        int[] ans = { Integer.MIN_VALUE };
        dfs(root, Integer.MIN_VALUE, ans);
        return ans[0];
    }

    private void dfs(Node root, int maxAnc, int[] ans) {
        if (root == null) {
            return;
        }
        if (maxAnc != Integer.MIN_VALUE) {
            ans[0] = Math.max(ans[0], maxAnc - root.data);
        }
        maxAnc = Math.max(maxAnc, root.data);
        dfs(root.left, maxAnc, ans);
        dfs(root.right, maxAnc, ans);
    }
}

Was this solution helpful?