###### tags: `leetcode` `medium` `Tree` `Depth-First Search` `Binary Tree`
# [1026. Maximum Difference Between Node and Ancestor](https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/)

## Description

Given the `root` of a binary tree, find the maximum value `v` for which there exist **different** nodes `a` and `b` where `v = |a.val - b.val|` and `a` is an ancestor of `b`.

A node `a` is an ancestor of `b` if either: any child of `a` is equal to `b` or any child of `a` is an ancestor of `b`.

## Examples
### Example1

**Input**: root = [8,3,10,1,6,null,14,null,null,4,7,13]
**Output**: 7
**Explanation**: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

### Example2

**Input**: root = [1,null,2,null,0,3]
**Output**: 3

## Constraints:

- The number of nodes in the tree is in the range `[2, 5000]`.
- $0 \leq Node.val \leq 10^5$

## Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TNODE;
int postOrder(TNODE *root, int max, int min){
    if(!root) return max-min;
    max = (root->val > max) ? root->val : max;
    min = (root->val < min) ? root->val : min;
    int left = postOrder(root->left, max, min);
    int right = postOrder(root->right, max, min);
    return left>right ? left : right;
}

int maxAncestorDiff(struct TreeNode* root){
    if(!root) return 0;
    return postOrder(root, root->val, root->val);
}

## Complexity

|Space |Time |
|- |- |
|$O(N)$|$O(N)$|

## Result

- Runtime : 0 ms, 100%
- Memory : 7.5 MB, 54.55%

## Notes

- Each difference is founded by the maximum and minimum of the path.
- Since each branch has the same subset notes of their parent, they inherit their parent's maximum and minimum and continue to update.
- We can not using call by address, because we need to maintain previous( parents' ) max/min for next branch counting.
- We use DFS( post-order traversal ) to scan whole tree, update max/min as we found `NULL` pointer. After then we just update the difference of current branch to parent and ancestors and they will compare their branches and return maximum difference.