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:
Visit the left subtree.
Visit the right subtree.
Find the minimum value in both subtrees.
Calculate:
current node - minimum descendant
Update the global maximum.
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.