# 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:

```python
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:

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

## Examples

Example 1:

```python
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:

```python
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

```python
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

```python
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` |