1. Problem Statement

Given the root of a binary tree, find the maximum difference between an ancestor node A and its descendant node B.

The required difference is:

Code
A - B

We need to maximize this value.

Example 1

Code
       5
      / \
     2   1

Possible ancestor-descendant differences:

Code
5 - 2 = 3
5 - 1 = 4

Therefore:

Code
Answer = 4

Example 2

Code
       1
      / \
     2   3
          \
           7

Here:

Code
1 - 2 = -1
1 - 3 = -2
3 - 7 = -4

The maximum value is:

Code
Answer = -1

Notice that the answer can be negative.

2. Main Idea

For every node, we need to know:

What is the smallest value among its descendants?

Because if the current node is 5 and its smallest descendant is 1:

Code
5 - 1 = 4

This gives the largest possible difference for that ancestor.

So during DFS, we will:

  1. Visit the left subtree.

  2. Visit the right subtree.

  3. Find the minimum value in both subtrees.

  4. Calculate:

Code
current node - minimum descendant

  1. Update the global maximum.

  2. Return the minimum value of the current subtree to its parent.

3. Java Code

Java
class Solution {

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

        findMin(root, ans);

        return ans[0];
    }

    int findMin(Node root, int[] ans) {

        // If node is null
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // If current node is a leaf
        if (root.left == null && root.right == null) {
            return root.data;
        }

        // Find minimum value in left subtree
        int leftMin = findMin(root.left, ans);

        // Find minimum value in right subtree
        int rightMin = findMin(root.right, ans);

        // Find minimum descendant
        int minDescendant = Math.min(leftMin, rightMin);

        // Calculate current node - minimum descendant
        ans[0] = Math.max(ans[0],
                          root.data - minDescendant);

        // Return minimum value in current subtree
        return Math.min(root.data, minDescendant);
    }
}

4. Understanding maxDiff()

Java
int maxDiff(Node root) {
    int[] ans = {Integer.MIN_VALUE};

    findMin(root, ans);

    return ans[0];
}

We initialize:

Java
int[] ans = {Integer.MIN_VALUE};

Why Integer.MIN_VALUE?

Because the answer can be negative.

For example:

Code
       1
      /
     2

The answer is:

Code
1 - 2 = -1

So we should not initialize the answer to 0.

If we did:

Java
int ans = 0;

we would incorrectly return 0 instead of -1.

The int[] is used so that the recursive function can update the same ans value.

5. Understanding the Base Case

Java
if (root == null) {
    return Integer.MAX_VALUE;
}

If there is no node, we return the largest possible integer.

Why?

Because we are looking for a minimum value.

For example, if a node has only a right child:

Code
      5
       \
        2

For the left subtree:

Java
leftMin = Integer.MAX_VALUE;

For the right subtree:

Java
rightMin = 2;

Then:

Java
Math.min(Integer.MAX_VALUE, 2)

gives:

Code
2

So this works naturally.

6. Handling Leaf Nodes

Java
if (root.left == null && root.right == null) {
    return root.data;
}

A leaf has no descendants.

For example:

Code
    1
     \
      2

Node 2 is a leaf.

We simply return:

Code
2

Its parent can then use 2 as its minimum descendant.

7. Finding the Minimum in the Left Subtree

Java
int leftMin = findMin(root.left, ans);

This recursively explores the entire left subtree.

For example:

Code
       5
      /
     2
    /
   1

When we call:

Java
findMin(2, ans)

it eventually discovers:

Code
1

and returns:

Code
leftMin = 1

8. Finding the Minimum in the Right Subtree

Java
int rightMin = findMin(root.right, ans);

Similarly, we find the minimum value in the right subtree.

Suppose:

Code
       5
      / \
     2   3
        /
       1

The minimum values are:

Code
Left subtree  = 2
Right subtree = 1

So:

Java
leftMin = 2;
rightMin = 1;

9. Finding the Minimum Descendant

Java
int minDescendant = Math.min(leftMin, rightMin);

We choose the smaller value.

For:

Code
leftMin = 2
rightMin = 1

we get:

Code
minDescendant = 1

Now we can calculate:

Code
current node - minimum descendant

10. Calculating the Difference

Java
ans[0] = Math.max(ans[0],
                  root.data - minDescendant);

Suppose:

Code
root.data = 5
minDescendant = 1

Then:

Code
5 - 1 = 4

So:

Java
ans[0] = Math.max(ans[0], 4);

If the current maximum was 3, it becomes:

Code
4

11. Why Do We Return Math.min(root.data, minDescendant)?

This is the most important part.

Java
return Math.min(root.data, minDescendant);

The parent node needs to know the minimum value anywhere inside this subtree.

For example:

Code
       5
      /
     2
    /
   1

For node 2:

Code
root.data = 2
minDescendant = 1

Therefore:

Java
return Math.min(2, 1);

returns:

Code
1

When we return to node 5, it knows:

Code
minimum value in my subtree = 1

Therefore:

Code
5 - 1 = 4

12. Complete Dry Run

Consider:

Code
       5
      / \
     2   1

Step 1 — Node 2

Node 2 is a leaf.

Return:

Code
2

Step 2 — Node 1

Node 1 is a leaf.

Return:

Code
1

Step 3 — Node 5

We now have:

Code
leftMin = 2
rightMin = 1

Therefore:

Code
minDescendant = min(2, 1)
               = 1

Calculate:

Code
5 - 1 = 4

Update:

Code
ans = 4

Finally return:

Code
min(5, 1) = 1

The final answer is:

Code
4

13. Why This Approach Is Efficient

A brute-force approach could try to compare every ancestor with every descendant. That can result in unnecessary repeated work.

Instead, our DFS calculates the minimum subtree value once.

For every node, we only perform constant-time operations:

Code
min()
max()
subtraction

Therefore:

Code
Time Complexity = O(n)

where n is the number of nodes.

The recursive call stack requires:

Code
Space Complexity = O(h)

where h is the height of the tree.

In the worst case, the tree can be completely skewed:

Code
1
 \
  2
   \
    3
     \
      4
       \
        5

Then:

Code
h = n

So the worst-case auxiliary space is:

Code
O(n)

14. Important Interview Point

The key observation is:

To maximize Ancestor - Descendant, for every ancestor we only need the minimum value in its descendant subtree.

So instead of storing every ancestor and descendant pair, we use post-order DFS:

Code
Left subtree
      ↓
Right subtree
      ↓
Current node

This allows the minimum descendant value to be calculated before processing the current ancestor.

Final Formula

For every non-leaf node:

Code
difference = node.data - minimum descendant

Then:

Code
answer = maximum of all differences

This gives an O(n) solution and handles negative answers correctly.