Maximum Difference Between Node and Ancestor
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.
One reading of this problem suggests checking every pair of nodes where one is an ancestor of the other. There is a shortcut. The absolute difference |a.val - b.val| is largest when one value is as large as possible and the other as small as possible. So for any given node, the ancestor that produces the biggest difference is either the one with the largest value or the one with the smallest value on the path from the root down to it.
That removes the need to compare against every ancestor individually. We track the minimum and maximum values along the current root-to-node path. At every node, we compute the difference against both extremes and update the answer.
Key Constraints:
2 <= number of nodes <= 5000→ An O(n^2) brute force stays under 25 million operations, so it passes. An O(n) solution is still available and simpler to reason about.0 <= Node.val <= 10^5→ All values are non-negative and bounded, so the difference between any two values fits in a 32-bit integer with no overflow risk.At least 2 nodes→ There is always at least one ancestor-descendant pair, so the answer is always defined.
Approach 1: Brute Force DFS (Check All Ancestors)
Intuition
For every node, compare it against each of its ancestors and track the maximum absolute difference. We maintain a list of ancestor values during a DFS traversal. 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 re-scan the whole path to find the best difference, even though only one new value was added since the parent 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).
The bottleneck is the per-node scan of the full ancestor list. Every ancestor value is not needed: the maximum difference at any node comes from comparing it against either the largest or the smallest ancestor on its path. The next approach carries only those two values down the tree.
Approach 2: Optimized DFS (Track Min and Max)
Intuition
For any node, the maximum |node.val - ancestor.val| occurs when the ancestor value is either the largest or the smallest on the path from root to that node. So instead of storing the full ancestor list, we pass two values down the tree: the minimum and maximum 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 child (one step past a leaf), we return max - min for that completed path.
Every node on a root-to-leaf path is an ancestor of every node below it on that path. Across all ancestor-descendant pairs on a single path, the largest |a.val - b.val| equals (path max) - (path min), because the difference between two numbers is largest when one is the maximum and the other the minimum of the set.
Every ancestor-descendant pair in the tree lies on at least one root-to-leaf path. Computing max - min for every root-to-leaf path and taking the overall maximum therefore covers all valid pairs and misses none.
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.