Maximum Difference Between Node and Ancestor — Solution
Maximum Difference Between Node and Ancestor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Difference Between Node and Ancestor is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, find the largest value |a.val - b.val| over all pairs of different nodes a and b where a is an ancestor of b.
Node a is an ancestor of b when b is a child of a, or a child of some node that is itself a descendant of a — that is, a lies on the path from the root down to b.
Example 1
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: Among all ancestor-descendant pairs the widest gap is between 8 and its descendant 1: |8 - 1| = 7.
Example 2
Input: root = [1,null,2,null,0,3]
Output: 3
Explanation: The chain is 1 → 2 → 0 → 3; the pair 0 (ancestor) and 3 (descendant) gives |0 - 3| = 3.
Example 3
Input: root = [6,6,6]
Output: 0
Explanation: Every value is the same, so every difference is 0.
Constraints
2 <= number of nodes <= 50000 <= Node.val <= 10^5
Hints for Maximum Difference Between Node and Ancestor
Hint 1
For a fixed node
b, the best ancestor to pair it with is either the smallest or the largest value on the path from the root tob.Hint 2
So it is enough to carry the minimum and the maximum seen so far down every root-to-node path.
Hint 3
When a path ends (you step past a leaf), the widest gap on that path is simply
max - min; the answer is the largest such gap over all paths.
How to solve Maximum Difference Between Node and Ancestor
Any ancestor-descendant pair lies on one root-to-leaf path, and on a path the widest gap is between its smallest and largest values. Carry the running minimum and maximum down each path and take max - min at its end.
Approach
- Start a depth-first walk at the root with
lo = hi = root.val. - At each node, update
lo = min(lo, node.val)andhi = max(hi, node.val). - When the walk reaches a null child, return
hi - lofor the path that just ended. - Each node returns the larger of its two children's results; the root's result is the answer.
Why it works
Both nodes of a pair lie on the path from the root to the deeper one, so every pair is covered by some root-to-leaf path. Conversely the minimum and maximum of a path are themselves an ancestor-descendant pair (or the same node, giving 0), so max - min is achievable and no pair on the path does better.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion, h the height
Pitfalls
- Comparing each node only with its parent misses gaps that span several levels.
- Carrying only the minimum (or only the maximum) misses pairs where the descendant is smaller than its ancestor.
Reference solution
Python
from typing import Optional
def maxAncestorDiff(root: Optional[TreeNode]) -> int:
def walk(node, lo, hi):
if node is None:
return hi - lo
lo = min(lo, node.val)
hi = max(hi, node.val)
return max(walk(node.left, lo, hi), walk(node.right, lo, hi))
return walk(root, root.val, root.val)Java
public static int maxAncestorDiff(TreeNode root) {
return diffWalk(root, root.val, root.val);
}
static int diffWalk(TreeNode node, int lo, int hi) {
if (node == null) return hi - lo;
lo = Math.min(lo, node.val);
hi = Math.max(hi, node.val);
return Math.max(diffWalk(node.left, lo, hi), diffWalk(node.right, lo, hi));
}C++
int diffWalk(TreeNode* node, int lo, int hi);
int maxAncestorDiff(TreeNode* root) {
return diffWalk(root, root->val, root->val);
}
int diffWalk(TreeNode* node, int lo, int hi) {
if (!node) return hi - lo;
lo = min(lo, node->val);
hi = max(hi, node->val);
return max(diffWalk(node->left, lo, hi), diffWalk(node->right, lo, hi));
}JavaScript
var maxAncestorDiff = function(root) {
return diffWalk(root, root.val, root.val);
};
var diffWalk = function(node, lo, hi) {
if (node === null) return hi - lo;
lo = Math.min(lo, node.val);
hi = Math.max(hi, node.val);
return Math.max(diffWalk(node.left, lo, hi), diffWalk(node.right, lo, hi));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals