Maximum Difference Between Node and Ancestor
Problem
root of a binary tree, consider every pair of
different nodes a and b where a is an
ancestor of b (it lies on the path from the root down to b).
Return the largest possible value of |a.val − b.val|.root = [5,9,2,null,null,0,7]Output5root = [1,null,2,null,0,3]Output3root = [4,4]Output02 ≤ nodes ≤ 5000 · 0 ≤ Node.val ≤ 105
Try it yourself
class Solution {
public int maxAncestorDiff(TreeNode root) {
}
}
min and
max of the current root-to-node path; at a leaf, max − min
is the best difference on that path.Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.
Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.
Open the Tree DFS guide →Approaches
Brute ForceEach Node vs. Its Whole Subtree
O(n · h)Space O(h)Treat every node as the ancestor in turn and scan all its descendants,
tracking the largest |ancestor − descendant|. Every valid pair
is examined, so the maximum is exact.
public int maxAncestorDiff(TreeNode root) { if (root == null) return 0; int best = Math.max(farthest(root.left, root.val), farthest(root.right, root.val)); best = Math.max(best, maxAncestorDiff(root.left)); return Math.max(best, maxAncestorDiff(root.right)); } // Largest |x.val - val| over every node x in this subtree. private int farthest(TreeNode node, int val) { if (node == null) return 0; int here = Math.abs(node.val - val); return Math.max(here, Math.max(farthest(node.left, val), farthest(node.right, val))); }
Correct by exhaustion, but a skewed tree (h = n) makes it O(n²).
BetterBottom-up Subtree Min/Max
O(n)Space O(h)Flip the roles: for a fixed ancestor, the best descendant is the minimum or
maximum of its subtree. A post-order DFS returns {min, max} of each
subtree; the parent compares its value against both children's ranges, then
merges them.
private int best; public int maxAncestorDiff(TreeNode root) { best = 0; if (root != null) range(root); return best; } // Returns {min, max} of the subtree rooted at node. private int[] range(TreeNode node) { int lo = node.val, hi = node.val; for (TreeNode child : new TreeNode[]{node.left, node.right}) { if (child == null) continue; int[] r = range(child); best = Math.max(best, Math.max(Math.abs(node.val - r[0]), Math.abs(node.val - r[1]))); lo = Math.min(lo, r[0]); hi = Math.max(hi, r[1]); } return new int[]{lo, hi}; }
Linear, but allocates a small array per node and splits logic across two directions.
OptimalTop-down Path Min/Max
O(n)Space O(h)Pass the minimum and maximum seen on the root-to-node path down the
recursion. All values on one root-to-leaf path are pairwise ancestor-related, so
the answer is the largest max − min over all such paths,
evaluated when the recursion falls off a leaf.
public int maxAncestorDiff(TreeNode root) { return root == null ? 0 : dfs(root, root.val, root.val); } private int dfs(TreeNode node, int lo, int hi) { if (node == null) return hi - lo; // spread of the finished path lo = Math.min(lo, node.val); hi = Math.max(hi, node.val); return Math.max(dfs(node.left, lo, hi), dfs(node.right, lo, hi)); }
One pass, two integers per call, no global state — the cleanest solution.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Each Node vs. Its Whole Subtree | O(n · h) | O(h) |
| Better | Bottom-up Subtree Min/Max | O(n) | O(h) |
| Optimal | Top-down Path Min/Max | O(n) | O(h) |
- Comparing only parent and child — the best pair can be many levels apart.
- Tracking just the path max (or just the min); you need both to cover |a − b|.
- Updating a global min/max instead of per-path values leaks state between sibling branches.
- Reduce the problem: for each node only the extreme ancestors matter.
- Point out that pairs on one root-to-leaf path are exactly the ancestor pairs.
- Mention both directions (top-down vs bottom-up) and pick the simpler one.