## Algorithm

Problem Name: 1026. Maximum Difference Between Node and Ancestor

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

Example 1:

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

Example 2:

```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 <= Node.val <= 105`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int maxAncestorDiff(TreeNode root) {
int maxDiff = 0;
while (!queue.isEmpty()) {
NodeValuePair removed = queue.remove();
TreeNode node = removed.node;
Integer minNodeValue = removed.minNodeValue;
Integer maxNodeValue = removed.maxNodeValue;
maxDiff = Math.max(maxDiff, Math.max(Math.abs(node.val - minNodeValue), Math.abs(node.val - maxNodeValue)));
Integer updatedMinNodeValue = Math.min(node.val, minNodeValue);
Integer updatedMaxNodeValue = Math.max(node.val, maxNodeValue);
if (node.left != null) {
}
if (node.right != null) {
}
}
return maxDiff;
}

private static class NodeValuePair {
private TreeNode node;
private Integer minNodeValue;
private Integer maxNodeValue;

public NodeValuePair(TreeNode node, Integer minNodeValue, Integer maxNodeValue) {
this.node = node;
this.minNodeValue = minNodeValue;
this.maxNodeValue = maxNodeValue;
}
}
}
``````
Copy The Code &

Input

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

Output

cmd
7

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxAncestorDiff = function(root) {
const arr = []
dfs(root, [], arr)
let res = Number.MIN_VALUE
for(let i = 0; i < arr.length; i++) {
let el = arr[i]
let max = Number.MIN_VALUE
let min = Number.MAX_VALUE
for(let j = 0; j < el.length; j++) {
if(el[j] < min) min = el[j]
if(el[j] > max) max = el[j]
}
if(Math.abs(max - min) > res) res = Math.abs(max - min)
}
return res
};

function dfs(node, arr, res) {
if(node == null) return
arr.push(node.val)
if(node.left === null && node.right === null) {
res.push(arr.slice(0))
return
}

dfs(node.left, arr.slice(0), res)
dfs(node.right, arr.slice(0), res)

}
``````
Copy The Code &

Input

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

Output

cmd
7

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
self.res = 0
def dfs(node):
mx = mn = node.val
if node.left:
lMn, lMx = dfs(node.left)
mx = max(mx, lMx)
mn = min(mn, lMn)
self.res = max(self.res, abs(lMn - node.val), abs(lMx - node.val))
if node.right:
rMn, rMx = dfs(node.right)
mx = max(mx, rMx)
mn = min(mn, rMn)
self.res = max(self.res, abs(rMn - node.val), abs(rMx - node.val))
return mn, mx
dfs(root)
return self.res
``````
Copy The Code &

Input

cmd
root = [1,null,2,null,0,3]

Output

cmd
3

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _1026_MaximumDifferenceBetweenNodeAndAncestor
{
public int MaxAncestorDiff(TreeNode root)
{
return MaxAncestorDiff(root, root.val, root.val);
}

private int MaxAncestorDiff(TreeNode node, int min, int max)
{
if (node == null) return max - min;

if (node.val < min)
min = node.val;
else if (node.val > max)
max = node.val;

return Math.Max(MaxAncestorDiff(node.left, min, max), MaxAncestorDiff(node.right, min, max));
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,null,2,null,0,3]

Output

cmd
3