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:

A - B

We need to maximize this value.

Example 1

       5
      / \
     2   1

Possible ancestor-descendant differences:

5 - 2 = 3
5 - 1 = 4

Therefore:

Answer = 4

Example 2

       1
      / \
     2   3
          \
           7

Here:

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

The maximum value is:

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:

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:

current node - minimum descendant

  1. Update the global maximum.

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

3. Java Code

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

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

    findMin(root, ans);

    return ans[0];
}

We initialize:

int[] ans = {Integer.MIN_VALUE};

Why Integer.MIN_VALUE?

Because the answer can be negative.

For example:

       1
      /
     2

The answer is:

1 - 2 = -1

So we should not initialize the answer to 0.

If we did:

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

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:

      5
       \
        2

For the left subtree:

leftMin = Integer.MAX_VALUE;

For the right subtree:

rightMin = 2;

Then:

Math.min(Integer.MAX_VALUE, 2)

gives:

2

So this works naturally.

6. Handling Leaf Nodes

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

A leaf has no descendants.

For example:

    1
     \
      2

Node 2 is a leaf.

We simply return:

2

Its parent can then use 2 as its minimum descendant.

7. Finding the Minimum in the Left Subtree

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

This recursively explores the entire left subtree.

For example:

       5
      /
     2
    /
   1

When we call:

findMin(2, ans)

it eventually discovers:

1

and returns:

leftMin = 1

8. Finding the Minimum in the Right Subtree

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

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

Suppose:

       5
      / \
     2   3
        /
       1

The minimum values are:

Left subtree  = 2
Right subtree = 1

So:

leftMin = 2;
rightMin = 1;

9. Finding the Minimum Descendant

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

We choose the smaller value.

For:

leftMin = 2
rightMin = 1

we get:

minDescendant = 1

Now we can calculate:

current node - minimum descendant

10. Calculating the Difference

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

Suppose:

root.data = 5
minDescendant = 1

Then:

5 - 1 = 4

So:

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

If the current maximum was 3, it becomes:

4

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

This is the most important part.

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

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

For example:

       5
      /
     2
    /
   1

For node 2:

root.data = 2
minDescendant = 1

Therefore:

return Math.min(2, 1);

returns:

1

When we return to node 5, it knows:

minimum value in my subtree = 1

Therefore:

5 - 1 = 4

12. Complete Dry Run

Consider:

       5
      / \
     2   1

Step 1 — Node 2

Node 2 is a leaf.

Return:

2

Step 2 — Node 1

Node 1 is a leaf.

Return:

1

Step 3 — Node 5

We now have:

leftMin = 2
rightMin = 1

Therefore:

minDescendant = min(2, 1)
               = 1

Calculate:

5 - 1 = 4

Update:

ans = 4

Finally return:

min(5, 1) = 1

The final answer is:

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:

min()
max()
subtraction

Therefore:

Time Complexity = O(n)

where n is the number of nodes.

The recursive call stack requires:

Space Complexity = O(h)

where h is the height of the tree.

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

1
 \
  2
   \
    3
     \
      4
       \
        5

Then:

h = n

So the worst-case auxiliary space is:

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:

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:

difference = node.data - minimum descendant

Then:

answer = maximum of all differences

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