DSA problem
Maximum Difference Between Node and Ancestor
Given the root of a binary tree, return the maximum value of |a.val - d.val| over every pair (a, d) where a is an ancestor of d (a strict ancestor — a is not d itself). Equivalently, for every root-to-leaf path, look at every pair of nodes (a higher one and a lower one) and report the largest difference seen anywhere in the tree.
The brute force enumerates every (ancestor, descendant) pair in O(n²). The elegant observation is that the maximum |a.val - d.val| along any single root-to-leaf path is exactly max(path) - min(path) — that is, the largest value on the path minus the smallest value on the path. So instead of tracking all values, we only need to carry the minimum and maximum seen so far as we descend.
This becomes a clean preorder DFS where each call receives (node, minSoFar, maxSoFar). When we hit null we return maxSoFar - minSoFar — the best span achievable along this branch. At an internal node we update minSoFar = min(minSoFar, node.val) and maxSoFar = max(maxSoFar, node.val), then return the larger of the two child results.
The algorithm runs in O(n) time and O(h) space. Note that the problem guarantees the tree has at least 2 nodes, so the answer is always at least 0 and is always realized by an actual ancestor-descendant pair.
Examples
root = [8,3,10,1,6,null,14,null,null,4,7,13]7root = [1,null,2,null,0,3]3root = [2,4,1]2Constraints
- The number of nodes in the tree is in the range [2, 5000].
- 0 <= Node.val <= 10^5
- The tree contains at least one ancestor-descendant pair.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.