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

Item	Meaning
Input	Root of a binary tree
Output	Maximum absolute difference between any node and its ancestor

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:

Ancestor	Node	Difference
8	1	7
3	7	4
8	14	6

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

Metric	Value	Why
Time	O(n)	Visit every node once
Space	O(h)	Recursion stack of tree height

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()

Test	Expected	Why
Standard tree	7	Pair (8, 1)
Right-skewed	3	The maximum ancestor-descendant difference is between ancestor 0 and descendant 3