LeetCode 1026: Maximum Difference Between Node and Ancestor

Problem Restatement

We are given the root of a binary tree.

For every pair of a node v and an ancestor u, we want to maximize:

abs(v.val - u.val)

We need to return the maximum such value over all valid ancestor-descendant pairs.

The official constraints state that the number of nodes is in [2, 5000] and 0 <= Node.val <= 10^5.

Input and Output

Function shape:

def maxAncestorDiff(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

root = [8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13]

Some ancestor-descendant pairs:

Maximum: 7.

Answer:

7

Key Insight

For any root-to-leaf path, the maximum difference between a node and one of its ancestors is achieved by the pair (max_along_path, min_along_path).

So we do a DFS while tracking the current minimum and maximum values seen on the path from the root.

At each leaf, compute max - min and update the global answer.

Algorithm

Define dfs(node, cur_min, cur_max):

1. If node is None, return cur_max - cur_min.
2. Update cur_min = min(cur_min, node.val) and cur_max = max(cur_max, node.val).
3. Return max(dfs(node.left, cur_min, cur_max), dfs(node.right, cur_min, cur_max)).

Correctness

At each node, cur_min and cur_max hold the minimum and maximum values of all ancestors plus the node itself on the current path.

The maximum difference that uses an ancestor from this path is cur_max - cur_min.

Since every node is visited, every ancestor-descendant pair is considered.

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        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)
            return max(dfs(node.left, cur_min, cur_max), dfs(node.right, cur_min, cur_max))

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

Testing

def run_tests():
    s = Solution()
    root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))), TreeNode(10, None, TreeNode(14, TreeNode(13))))
    assert s.maxAncestorDiff(root) == 7

    root2 = TreeNode(1, None, TreeNode(2, None, TreeNode(0, TreeNode(3))))
    assert s.maxAncestorDiff(root2) == 3

    print("all tests passed")

run_tests()