Maximum Difference Between Node and Ancestor
Last Updated: April 1, 2026
Understanding the Problem
We have a binary tree and need to find the maximum absolute difference between any ancestor-descendant pair. The pair does not have to be a direct parent-child relationship. An ancestor can be many levels above the descendant.
A naive reading might suggest we need to check every possible pair of nodes where one is an ancestor of the other. But notice something: the absolute difference |a.val - b.val| is maximized when one value is as large as possible and the other is as small as possible. So for any given node, the best ancestor to pair it with is either the one with the largest value or the one with the smallest value on the path from the root down to it.
This key observation means we do not need to compare against every ancestor individually. We just need to track the minimum and maximum values along the current root-to-node path. At every node, we can compute the difference against both extremes and update our global answer.
Key Constraints:
2 <= number of nodes <= 5000→ With at most 5000 nodes, even an O(n^2) brute force would run in under 25 million operations, which is fine. But we can do better with O(n).0 <= Node.val <= 10^5→ All values are non-negative. The absolute difference between any two node values fits comfortably in an integer.At least 2 nodes→ There is always at least one ancestor-descendant pair, so the answer is always well-defined.
Approach 1: Brute Force DFS (Check All Ancestors)
Intuition
The most direct approach: for every node, compare it against every one of its ancestors and track the maximum absolute difference. We can do this by maintaining a list of ancestor values as we traverse the tree using DFS. At each node, we iterate through the entire ancestor list and compute the absolute difference with each ancestor.
This is correct but does redundant work. At each node, we scan the entire path to find the best difference, even though we only added one new value since the last node.
Algorithm
- Start a DFS from the root with an empty list representing the current path of ancestor values.
- At each node, iterate through the ancestor list and compute |node.val - ancestor.val| for each ancestor. Update the global maximum difference.
- Add the current node's value to the path list.
- Recurse into the left and right children.
- After both recursive calls, remove the last element from the path list (backtrack).
- Return the global maximum difference.
Example Walkthrough
Code
- Time Complexity: O(n * h). We visit each of the n nodes once, and at each node we scan through all its ancestors, which is at most h (the height of the tree). On a balanced tree h = log n, so this is O(n log n). On a skewed tree h = n, so worst case is O(n^2).
- Space Complexity: O(h). The ancestor list holds at most h values, and the recursion stack also goes h levels deep. On a balanced tree this is O(log n), on a skewed tree O(n).
This approach works correctly but scans the entire ancestor list at every node. We do not actually need every ancestor value. The maximum absolute difference at any node comes from comparing it against either the largest or smallest ancestor. What if we just tracked those two extremes?
Approach 2: Optimized DFS (Track Min and Max)
Intuition
Here is the insight that unlocks the optimal solution. For any node, the maximum |node.val - ancestor.val| happens when the ancestor value is either the largest or smallest on the path from root to that node. The absolute difference is maximized at the extremes.
So instead of storing the full ancestor list, we just pass two values down the tree: the minimum and maximum values seen so far on the current root-to-node path. At each node, we update the min and max before recursing deeper. When we reach a null node (beyond a leaf), we return max - min for that path.
The correctness relies on a simple observation: for any root-to-leaf path, every node on that path is an ancestor of every node below it. The maximum |a.val - b.val| across all ancestor-descendant pairs on a single path equals (path max) - (path min). This is because the absolute difference between two numbers is maximized when one is the global max and the other is the global min.
By computing max - min for every root-to-leaf path and taking the overall maximum, we cover all possible ancestor-descendant pairs in the tree. Every such pair lies on some root-to-leaf path, so we never miss a valid pair.
Algorithm
- Start a DFS from the root, passing the root's value as both the initial min and max.
- At each node, update the running min and max to include the current node's value.
- If the node is null (beyond a leaf), return max - min as the result for this path.
- Otherwise, recurse into the left and right children, passing the updated min and max.
- Return the larger result from the two children.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once, doing O(1) work at each node (two comparisons, two min/max updates). No scanning of ancestor lists.
- Space Complexity: O(h). The recursion stack goes as deep as the tree height. On a balanced tree this is O(log n), on a skewed tree O(n). We use no extra data structures beyond the recursion stack.