# Maximum Difference Between Node and Ancestor
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-difference-between-node-and-ancestor)
Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-between-node-and-ancestor
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-difference-between-node-and-ancestor/image0.jpg) 

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

![](https://assets.glich.co/dsa/maximum-difference-between-node-and-ancestor/image1.jpg) 

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

# Approaches
## Brute Force with Nested Traversal
This approach uses a straightforward brute-force method. It iterates through each node of the tree, considering it as an ancestor `a`. For each such ancestor, it then performs another traversal through all of its descendants `b`. For every ancestor-descendant pair `(a, b)`, it calculates the absolute difference of their values, `|a.val - b.val|`, and updates a global maximum value. This ensures that every possible pair is checked.
**Time:** O(N^2) in the worst case (for a skewed tree) and O(N log N) in the best case (for a balanced tree). For each of the N nodes, we traverse its subtree. The sum of all subtree sizes is O(N^2) in the worst case. · **Space:** O(N) in the worst case. The space is dominated by the recursion stack depth. For a skewed tree, the depth of both the outer and inner traversals can be up to N.
**Pros:** Conceptually simple and easy to follow.; Guaranteed to be correct as it checks all possibilities.
**Cons:** Highly inefficient due to its time complexity, which is quadratic in the worst case.; Performs many redundant calculations. The difference between a node and its grandparent is calculated when the grandparent is the ancestor, and again when the parent is the ancestor (as part of its descendant traversal).
### Explanation
The core idea is to systematically check every valid ancestor-descendant pair. We can implement this using two nested traversals. The outer traversal selects a node to be the ancestor. The inner traversal explores the entire subtree of that ancestor node. 

For example, if we have a DFS function `outer_dfs(node)` that traverses the whole tree. When `outer_dfs` is at a node `u`, we call another function `inner_dfs(u, v)` which starts with `v=u` and explores all nodes in the subtree of `u`. Inside `inner_dfs`, we calculate `|u.val - v.val|` and update our answer. This process guarantees that we compare every node with all of its descendants.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDifference = 0;

    public int maxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Outer traversal to select each node as a potential ancestor
        traverseForAllAncestors(root);
        return maxDifference;
    }

    private void traverseForAllAncestors(TreeNode ancestorNode) {
        if (ancestorNode == null) {
            return;
        }
        // For the current ancestor, find the max difference with all its descendants
        findMaxDiffWithDescendants(ancestorNode, ancestorNode);
        
        // Continue to other nodes
        traverseForAllAncestors(ancestorNode.left);
        traverseForAllAncestors(ancestorNode.right);
    }

    private void findMaxDiffWithDescendants(TreeNode ancestor, TreeNode descendant) {
        if (descendant == null) {
            return;
        }
        
        // Calculate and update the maximum difference
        maxDifference = Math.max(maxDifference, Math.abs(ancestor.val - descendant.val));
        
        // Recurse for descendants
        findMaxDiffWithDescendants(ancestor, descendant.left);
        findMaxDiffWithDescendants(ancestor, descendant.right);
    }
}
```
### Algorithm
- Initialize a global variable `maxDifference` to 0.
- Create a main traversal function, e.g., `traverseForAllAncestors(node)`, which will iterate through every node in the tree using DFS.
- For each `node` visited by this main traversal, consider it as a potential `ancestor`.
- From this `ancestor` node, start a second, inner DFS traversal, e.g., `findMaxDiffWithDescendants(ancestor, descendant)`.
- In the inner traversal, for every `descendant` node in the subtree of the `ancestor`, calculate the absolute difference: `diff = |ancestor.val - descendant.val|`.
- Update the global `maxDifference` with this `diff` if it's larger than the current maximum.
- After the outer traversal completes, `maxDifference` will hold the result.

## Optimal Single Pass DFS
A much more efficient solution involves a single pass through the tree. As we traverse from the root down to the leaves, we can keep track of the minimum and maximum values encountered on the path so far. For any node, the maximum difference with an ancestor must be the difference between the node's value and either the minimum or maximum value seen on the path from the root to that node. This avoids the need for a nested traversal.
**Time:** O(N), where N is the number of nodes in the tree. Each node is processed exactly once during the traversal. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H = N, leading to O(N) space. For a balanced tree, H = log N, leading to O(log N) space.
**Pros:** Optimal time complexity as it visits each node only once.; Space efficient, especially for balanced trees.; Elegant and concise implementation.
**Cons:** The recursive implementation uses stack space, which could lead to a `StackOverflowError` for extremely deep trees (though not an issue with the given constraints).
### Explanation
We can implement this with a single recursive Depth-First Search (DFS) function. This function, let's call it `findMaxDiff(node, currentMin, currentMax)`, will traverse the tree while maintaining the minimum and maximum values seen on the ancestor path.

When visiting a `node`:
1. We have `currentMin` and `currentMax` from its ancestors.
2. The maximum difference involving this `node` and one of its ancestors is `max(|node.val - currentMin|, |node.val - currentMax|)`. We update our global answer with this value.
3. Before recursing to the children, we update the path's min/max values to include the current node: `newMin = min(currentMin, node.val)` and `newMax = max(currentMax, node.val)`.
4. We then call the function on the left and right children with these new min/max values.

The process starts at the root, where the initial `currentMin` and `currentMax` are both `root.val`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDifference = 0;

    public int maxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        findMaxDiff(root, root.val, root.val);
        return maxDifference;
    }

    private void findMaxDiff(TreeNode node, int currentMin, int currentMax) {
        if (node == null) {
            return;
        }

        int potentialMaxDiff = Math.max(Math.abs(node.val - currentMin), Math.abs(node.val - currentMax));
        maxDifference = Math.max(maxDifference, potentialMaxDiff);

        int newMin = Math.min(currentMin, node.val);
        int newMax = Math.max(currentMax, node.val);

        findMaxDiff(node.left, newMin, newMax);
        findMaxDiff(node.right, newMax, newMax);
    }
}
```
### Algorithm
- The key insight is that for any node `b`, the maximum difference `|a.val - b.val|` where `a` is an ancestor will occur when `a.val` is either the minimum or the maximum value among all its ancestors.
- We can perform a single top-down DFS traversal.
- We define a recursive helper function `dfs(node, currentMin, currentMax)`.
- `currentMin` and `currentMax` track the minimum and maximum values on the path from the root to the current `node`.
- At each `node`, we calculate the difference between `node.val` and both `currentMin` and `currentMax`, and update a global maximum difference.
- We then update `currentMin` and `currentMax` with `node.val` to include the current node in the path for its children.
- We recursively call the function for the left and right children with the updated min and max values.
- The initial call is `dfs(root, root.val, root.val)`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int ans ; public int MaxAncestorDiff ( TreeNode root ) { dfs ( root , root . val , root . val ); return ans ; } private void dfs ( TreeNode root , int mi , int mx ) { if ( root == null ) { return ; } int x = Math . Max ( Math . Abs ( mi - root . val ), Math . Abs ( mx - root . val )); ans = Math . Max ( ans , x ); mi = Math . Min ( mi , root . val ); mx = Math . Max ( mx , root . val ); dfs ( root . left , mi , mx ); dfs ( root . right , mi , mx ); } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int maxAncestorDiff ( TreeNode root ) { dfs ( root , root . val , root . val ); return ans ; } private void dfs ( TreeNode root , int mi , int mx ) { if ( root == null ) { return ; } int x = Math . max ( Math . abs ( mi - root . val ), Math . abs ( mx - root . val )); ans = Math . max ( ans , x ); mi = Math . min ( mi , root . val ); mx = Math . max ( mx , root . val ); dfs ( root . left , mi , mx ); dfs ( root . right , mi , mx ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxAncestorDiff =
  function (root) {
    let ans = 0;
    const dfs = (root, mi, mx) => {
      if (!root) {
        return;
      }
      ans = Math.max(ans, Math.abs(mi - root.val), Math.abs(mx - root.val));
      mi = Math.min(mi, root.val);
      mx = Math.max(mx, root.val);
      dfs(root.left, mi, mx);
      dfs(root.right, mi, mx);
    };
    dfs(root, root.val, root.val);
    return ans;
  };

```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxAncestorDiff ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root , mi , mx ): if root is None : return nonlocal ans ans = max ( ans , abs ( mi - root . val ), abs ( mx - root . val )) mi = min ( mi , root . val ) mx = max ( mx , root . val ) dfs ( root . left , mi , mx ) dfs ( root . right , mi , mx ) ans = 0 dfs ( root , root . val , root . val ) return ans
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxAncestorDiff ( TreeNode * root ) { int ans = 0 ; function < void ( TreeNode * , int , int ) > dfs = [ & ]( TreeNode * root , int mi , int mx ) { if ( ! root ) { return ; } ans = max ({ ans , abs ( mi - root -> val ), abs ( mx - root -> val )}); mi = min ( mi , root -> val ); mx = max ( mx , root -> val ); dfs ( root -> left , mi , mx ); dfs ( root -> right , mi , mx ); }; dfs ( root , root -> val , root -> val ); return ans ; } };
```