Maximum Difference Between Node and Ancestor: Tree Min/Max Tracking

You are given the root of a binary tree. Find the maximum value v such that there exist two different nodes a and b where a is an ancestor of b and v = |a.val - b.val|. This is LeetCode 1026: Maximum Difference Between Node and Ancestor, a medium-difficulty tree problem that teaches you how to pass accumulated state down through a DFS.

Why this problem matters

Many tree problems ask you to compute some property that depends on the relationship between a node and one of its ancestors. Maybe it is the sum of all values on the path from root to leaf, or the minimum value encountered so far. This problem is one of the cleanest examples of that pattern. You need to track two pieces of information, the minimum and maximum, as you walk from root to leaf.

Once you see how to thread min and max values through a DFS call, you can apply the same technique to a whole family of tree problems. The idea of "pass state down, compute the answer at the leaves" shows up repeatedly in interview questions.

What makes this problem especially nice is that the brute-force approach (checking every ancestor-descendant pair) is O(n^2), but the DFS approach solves it in a single O(n) pass. The trick is realizing that you do not need to compare every pair. You only need the extreme values along each path.

The key insight

As you DFS from the root toward the leaves, keep track of the smallest and largest values you have seen so far on the current path. At any node, the maximum possible difference involving that node and one of its ancestors is simply max_so_far - min_so_far. You do not need to remember every ancestor value, just the two extremes.

When you reach a leaf, the best candidate for that entire root-to-leaf path is max_val - min_val. The overall answer is the maximum of this value across all root-to-leaf paths.

Why does this work? Because the maximum |a.val - b.val| along any path must involve either the largest or smallest value on that path. If you track both, you automatically capture the best pair.

The solution

def max_ancestor_diff(root):
    def dfs(node, cur_min, cur_max):
        if node is None:
            return cur_max - cur_min
        cur_min = min(cur_min, node.val)
        cur_max = max(cur_max, node.val)
        left = dfs(node.left, cur_min, cur_max)
        right = dfs(node.right, cur_min, cur_max)
        return max(left, right)

    return dfs(root, root.val, root.val)

Here is what each piece does:

• dfs(node, cur_min, cur_max) recurses through the tree, carrying the minimum and maximum values seen on the path from the root to the current node.
• if node is None: return cur_max - cur_min is the base case. When we go past a leaf, we have a complete path. The best difference on this path is the gap between the largest and smallest values.
• cur_min = min(cur_min, node.val) updates the running minimum with the current node's value.
• cur_max = max(cur_max, node.val) does the same for the running maximum.
• We recurse into both children, passing the updated min and max, and return whichever subtree produced the larger difference.

Visual walkthrough

Let's trace the DFS through the tree [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]. At each step, notice how the min and max values evolve as we go deeper.

The critical moment is Step 3. When we reach node 1 (a leaf), the running min has dropped to 1 while max stayed at 8. That gives us 8 - 1 = 7, which turns out to be the global best. The right subtree produces candidates like 14 - 8 = 6, which is close but does not beat 7.

Notice that we never had to compare node 1 against every single ancestor individually. By carrying min and max down the path, we implicitly considered every ancestor-descendant pair on that path in O(1) time per node.

Complexity analysis

Time is O(n). Every node is visited exactly once, and we do O(1) work at each node (two comparisons and two min/max updates).

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree (like a linked list), h = n.

No extra data structures are needed. The min and max values are just two integers passed as function arguments.

The building blocks

1. Pre-order min/max state passing

The core technique is passing accumulated state (min and max) from parent to child during a pre-order DFS. Each node updates the state and passes it downward. The skeleton looks like this:

def dfs(node, state):
    if node is None:
        return base_value(state)
    state = update(state, node.val)
    left = dfs(node.left, state)
    right = dfs(node.right, state)
    return combine(left, right)

This same pattern appears in Sum Root to Leaf Numbers (where the state is the accumulated number), Path Sum problems (where the state is the remaining target), and any problem that needs information about the path from root to the current node. The key detail here is that state flows downward only, never upward. Each child receives the state from its parent, not from its sibling.

2. Leaf-level result aggregation

Instead of computing a result at every internal node, we compute it only at the leaves and bubble the best result back up. The aggregation function here is max(left, right), which picks the best result from either subtree.

if node is None:
    return cur_max - cur_min

left = dfs(node.left, cur_min, cur_max)
right = dfs(node.right, cur_min, cur_max)
return max(left, right)

This is simpler than the global-max-with-local-return pattern used in problems like Diameter of Binary Tree, because there is no separate "global update" at each node. The result naturally propagates upward through return values. You only need to compute the answer at the leaves because the min/max gap can only grow (or stay the same) as you move deeper down a path.

Edge cases

• Single node tree: The root has no descendants, so the DFS immediately hits null children. cur_max - cur_min = root.val - root.val = 0. The answer is 0.
• Skewed tree (linked list shape): The tree has only one root-to-leaf path. The answer is simply the difference between the largest and smallest values on that single path.
• All nodes have the same value: Every path has min = max, so the answer is 0. The algorithm handles this naturally.
• Maximum difference at a deep leaf: The best pair might involve the root and a deeply nested leaf. The algorithm catches this because it carries the root's value in min or max all the way down.
• Negative-free guarantee: The problem states all node values are between 0 and 100,000, so we do not need to worry about negative values complicating the min/max logic.

From understanding to recall

You now see why tracking min and max along each DFS path is enough to find the best ancestor-descendant difference. You understand that the gap can only grow as you descend, so the leaves are where you check the final answer. The solution is short and elegant.

But will you remember the details next week? Will you recall that the base case returns cur_max - cur_min instead of 0? Will you remember to initialize both cur_min and cur_max to root.val instead of infinity? These small details matter under interview pressure.

Spaced repetition locks in the pattern. You practice writing the solution from scratch at increasing intervals, first after a day, then three days, then a week. Each time you reconstruct the DFS signature, the base case, and the min/max update from memory. After a few repetitions, the "pass min/max down, compute at the leaf" pattern becomes second nature, and you can apply it to any tree problem that needs path-level state.

Related posts

• Binary Tree Maximum Path Sum - another tree problem tracking values along paths
• Diameter of Binary Tree - DFS with state tracking returning aggregate results
• Sum Root to Leaf Numbers - pre-order state passing pattern

If you want to build real fluency with tree patterns like min/max tracking, ancestor-descendant relationships, and DFS state passing, give CodeBricks a try. Our spaced repetition system breaks each problem into reusable building blocks so you drill the patterns that actually transfer across problems.