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.

Examples

Example 1:

graph TD
    H(8)
    H --- C(3) & J(10)
    C(3) --- A(1)
    C(3) --- F(6)
    F --- D(4) & G(7)
    J ~~~ N1:::hidden
    J --- N(14)
    N --- M(13)
    N ~~~ N2:::hidden

classDef hidden display:none
  
1
2
3
4
5
6
7
8

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:

graph TD
    A(1)
    A ~~~ N1:::hidden
    A --- B(2)
    B ~~~ N2:::hidden
    B --- F(0)
    F --- C(3)
    F ~~~ N3:::hidden

classDef hidden display:none
  
1
2

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

Solution

Method 1 - DFS

To solve this problem, we need to find the maximum difference between the values of a and b such that a is an ancestor of b in a binary tree. This essentially requires traversing the tree while keeping track of the minimum and maximum values encountered along the path from the root to each node. The difference between these values at any point will help in determining the desired v.

The main idea is a depth-first traversal (DFS), where we recursively explore the tree, updating the minimum and maximum values encountered so far.

Here is the approach:

  • Start at the root and initialise the current minimum (cur_min) and maximum (cur_max) to the root’s value.
  • For each child node, update the current minimum and maximum based on the child’s value, and compute the absolute difference between the node’s value and the current minimum or maximum.
  • Propagate the updated values down the tree.
  • Keep track of the global maximum difference (ans) using these values.
  • Base Case:
    • If the node is null, return immediately (there’s no further subtree to explore).
  • Recursive Calculations:
    • Calculate the max difference for the left and right subtrees.
    • Add the returned values to the overall result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    
    private int dfs(TreeNode node, int curMin, int curMax) {
        if (node == null) {
            return curMax - curMin;
        }
        
        curMin = Math.min(curMin, node.val);
        curMax = Math.max(curMax, node.val);
        
        int leftDiff = dfs(node.left, curMin, curMax);
        int rightDiff = dfs(node.right, curMin, curMax);
        
        return Math.max(leftDiff, rightDiff);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], cur_min: int, cur_max: int) -> int:
            if not node:
                return cur_max - cur_min
            
            cur_min = min(cur_min, node.val)
            cur_max = max(cur_max, node.val)
            
            left_diff = dfs(node.left, cur_min, cur_max)
            right_diff = dfs(node.right, cur_min, cur_max)
            
            return max(left_diff, right_diff)
        
        return dfs(root, root.val, root.val)

Complexity

  • ⏰ Time complexity: O(n). Each node is visited exactly once during the DFS traversal of the tree.
  • 🧺 Space complexity: O(h). The recursion depth will be equal to the height of the binary tree (h). In the worst case, h = n for a skewed tree.