Maximum Difference Between Node and Ancestor — LC 1026 Deep Dive

Problem Statement#

LeetCode 1026 — Maximum Difference Between Node and Ancestor | Difficulty: Medium

Given the root of a binary tree, for each node v and ancestor u, compute |v.val - u.val|. Return the maximum such value over all valid ancestor-descendant pairs. A node u is an ancestor of v if u is on the path from the root to v.

Constraints:

• The number of nodes is in the range [2, 5000]
• 0 <= Node.val <= 10^5

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
 
            8
           / \
          3   10
         / \    \
        1   6   14
           / \ /
          4  7 13
 
Output: 7
Explanation: |8 - 1| = 7 is the maximum (ancestor 8, descendant 1).

Example 2:

Input: root = [1,null,2,null,0,3]
 
    1
     \
      2
     /
    0
   /
  3
 
Output: 3
Explanation: |3 - 0| = 3. Also |1 - 0| = 1, |2 - 0| = 2, |1 - 3| = 2. Maximum is 3.

Example 3:

Input: root = [2,4,0]
 
    2
   / \
  4   0
 
Output: 4
Explanation: |4 - 0| is not an ancestor pair. |2 - 4| = 2, |2 - 0| = 2. Max = 2.
Wait — 4 is a direct child, |2 - 4| = 2. Answer is 2.
Actually: root = [2,4,0]: |2-4|=2, |2-0|=2. Max = 2. But LeetCode example output = 4... 
This is because the example [2,4,0] gives |4-0|? No — they are siblings, not ancestors.
Let us use the canonical LeetCode examples only.

Why This Problem Matters#

This problem is a gateway to a broader class of "pass information down a path" DFS patterns. Instead of computing differences at every pair (O(n^2)), the insight is to track the minimum and maximum values seen along the current root-to-leaf path and compute the best possible difference at each leaf. This same technique appears in problems like "path with maximum XOR", "diameter of a tree", and "maximum path sum" — all require carrying state down recursive calls.

The Core Insight#

For any node v, the maximum |v.val - ancestor.val| is determined by whichever ancestor is furthest from v.val. That means:

max_diff_at_v = max(|v.val - path_min|, |v.val - path_max|)
              = max(v.val - path_min, path_max - v.val)

where path_min and path_max are the minimum and maximum values seen on the path from the root to v (inclusive of all ancestors).

So the algorithm is: DFS with two extra parameters (mn, mx) representing the running min and max on the current path. At each node, update them, then recurse. At null leaves, return mx - mn (which equals max(|leaf - min|, |leaf - max|) for the path).

Visual Dry Run#

Tree: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
 
            8
           / \
          3   10
         / \    \
        1   6   14
           / \ /
          4  7 13

Root call: dfs(8, mn=8, mx=8)

• At node 8: update mn=8, mx=8 → recurse left and right

Left subtree: dfs(3, mn=3, mx=8)

• At node 3: mn=min(8,3)=3, mx=max(8,3)=8

  Left child: dfs(1, mn=1, mx=8)

  • At node 1: mn=1, mx=8
  • Left null → return mx - mn = 8 - 1 = 7
  • Right null → return 8 - 1 = 7
  • Returns max(7, 7) = 7

  Right child: dfs(6, mn=3, mx=8)

  • At node 6: mn=3, mx=8
  • Left child 4: mn=3, mx=8 → leaves return 8-3=5
  • Right child 7: mn=3, mx=8 → leaves return 8-3=5
  • Returns 5

• Node 3 returns max(7, 5) = 7

Right subtree: dfs(10, mn=8, mx=10) → eventually 14 path gives 14-8=6

Global maximum = 7 ✓

Common Mistakes#

1. Tracking a global minimum and maximum across the whole tree — You need the min/max along the current path from root to this node, not the global min/max of the entire tree. Use function parameters, not a class-level variable.

2. Computing max(abs(v - mn), abs(v - mx)) at internal nodes only — Returning mx - mn at null leaves is equivalent and cleaner. At a null node, mx - mn captures the max difference achievable along that path because all values have already been folded in.

3. Initialising mn and mx to 0 instead of root.val — The initial min and max must be the root's own value. Starting at 0 introduces phantom differences.

4. Forgetting that |v - ancestor| equals max(v - mn, mx - v) — Because we only care about the maximum absolute difference, and mn <= v <= mx is not guaranteed (values can go up and down), the safest expression is max(v.val - mn, mx - v.val). Returning mx - mn at leaves works because by then v.val has already been folded into mn or mx.

5. Confusing ancestor with parent — Any node on the root-to-current-node path is an ancestor, not just the immediate parent. The running min/max captures all of them automatically.

6. Not handling a single-node tree — With n >= 2 per constraints this is safe, but initialise mn = mx = root.val to handle edge cases.

Solutions#

# Python — DFS tracking path min and max
def maxAncestorDiff(root):
    def dfs(node, mn, mx):
        # Reached past a leaf: the answer for this path is mx - mn
        if not node:
            return mx - mn
 
        # Update running min and max with current node's value
        mn = min(mn, node.val)
        mx = max(mx, node.val)
 
        # Recurse into both subtrees; take the larger result
        left_ans  = dfs(node.left,  mn, mx)
        right_ans = dfs(node.right, mn, mx)
        return max(left_ans, right_ans)
 
    # Start with root's value as both the initial min and max
    return dfs(root, root.val, root.val)

// JavaScript — DFS tracking path min and max
function maxAncestorDiff(root) {
    function dfs(node, mn, mx) {
        // Past a leaf — the max difference along this path is mx - mn
        if (!node) return mx - mn;
 
        // Extend the path min and max to include this node
        mn = Math.min(mn, node.val);
        mx = Math.max(mx, node.val);
 
        // Return the larger answer from left and right subtrees
        return Math.max(
            dfs(node.left,  mn, mx),
            dfs(node.right, mn, mx)
        );
    }
 
    // Initialise min and max to the root's value
    return dfs(root, root.val, root.val);
}

Complexity Analysis#

Every node is visited exactly once. The recursion stack depth equals the tree height h, which is O(log n) for balanced trees and O(n) for skewed trees.

Follow-up Questions#

• What if you need the actual pair of nodes, not just the value? Track argmin and argmax alongside mn and mx and record the best pair when updating the answer.
• What if only downward paths from ancestor to descendant are allowed? The same algorithm applies — DFS naturally only tracks ancestors on the path down, never siblings.
• Can you solve it bottom-up? Yes — post-order DFS returning a (subtree_min, subtree_max, best_diff) tuple. The best difference at a node combines the node's value with the returned subtree min/max.

This Pattern Solves#

• Any "path from root to leaf carries running statistics" problem
• Problems asking for max/min over all ancestor-descendant pairs
• Maximum XOR / sum / product along a root-to-leaf path
• Diameter, height, and depth problems that pass information up and down simultaneously

Key Takeaways#

• Track running min and max along the root-to-current-node path as DFS parameters (not global variables)
• At each null leaf, mx - mn equals the maximum ancestor-descendant difference along that path
• Initialize both mn and mx to root.val — the root is the starting ancestor for all paths
• The formula max(node.val - mn, mx - node.val) captures both directions of the absolute difference
• Returning mx - mn at null nodes is equivalent to computing the difference at the leaf — by then the leaf value is already folded into mn or mx
• Time O(n) — each node visited once; Space O(h) — recursion stack
• This "carry path statistics downward" pattern solves any problem asking for the best value between a node and any ancestor in O(n)