Leetcode 1026. Maximum Difference Between Node and Ancestor

Problem Explanation:

Suppose we are given the root of a binary tree. Our task is to find the maximum value of difference V for which there exists different nodes A and B such that V = |A.val - B.val| and A is an ancestor of B. Here, 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.

For example, consider the following binary tree:

1
2
3    8
4   / \
5  3   10
6 / \    \
71   6    14
8   / \   /
9  4   7 13

Here, some of the differences between ancestor and descendant nodes are as follows:

• |8 - 3| = 5
• |3 - 7| = 4
• |8 - 1| = 7
• |10 - 13| = 3

The maximum difference obtained is 7 from |8 - 1| = 7, and thus this value will be the output.

Solution Approach:

The problem can be solved using Depth-first Search(DFS), a tree traversal algorithm. During our traversal, we keep track of the minimum and maximum values we have seen so far. For every node we visit, we update the maximum difference with the maximum of current maximum difference and the difference between the current node's value and the minimum and maximum values.

Java Solution:

1
2java
3class Solution {
4    public int maxAncestorDiff(TreeNode root) {
5        // Base case: If root is null, return 0
6        if (root == null)
7            return 0;
8        // Call the helper method with root's value as min and max initially
9        return dfs(root, root.val, root.val);
10    }
11  
12    private int dfs(TreeNode node, int min_val, int max_val) {
13        // Base case: If node is null, return the difference
14        if (node == null)
15            return max_val - min_val;
16        // Update min and max values
17        min_val = Math.min(min_val, node.val);
18        max_val = Math.max(max_val, node.val);
19        // Recurse for left and right subtree and return the maximum of all differences
20        return Math.max(dfs(node.left, min_val, max_val), dfs(node.right, min_val, max_val));
21    }
22}

Python Solution:

1
2python
3class Solution:
4    def maxAncestorDiff(self, root: TreeNode) -> int:
5        # Define a helper function to perform DFS
6        def dfs(node, min_val, max_val):
7            # Base case: If node is null, return the difference
8            if not node:
9                return max_val - min_val
10            # Update min and max values
11            min_val = min(min_val, node.val)
12            max_val = max(max_val, node.val)
13            # Recurse for left and right subtree and return the maximum of all differences
14            return max(dfs(node.left, min_val, max_val), dfs(node.right, min_val, max_val))
15        # Base case: If root is null, return 0
16        if not root:
17            return 0
18        # Call the helper method with root's value as min and max initially
19        return dfs(root, root.val, root.val);

JavaScript Solution:

1
2javascript
3var maxAncestorDiff = function(root) {
4    return dfs(root, root.val, root.val);
5    
6    function dfs(node, min_val, max_val){
7        if (!node) return max_val - min_val;
8        min_val = Math.min(min_val, node.val);
9        max_val = Math.max(max_val, node.val);
10        return Math.max(dfs(node.left, min_val, max_val), dfs(node.right, min_val, max_val));
11    }
12};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int maxAncestorDiff(TreeNode* root) {
6        return dfs(root, root->val, root->val);
7    }
8private:
9    int dfs(TreeNode* node, int min_val, int max_val){
10        if (!node) return max_val - min_val;
11        min_val = min(min_val, node->val);
12        max_val = max(max_val, node->val);
13        return max(dfs(node->left, min_val, max_val), dfs(node->right, min_val, max_val));
14    }
15};

C# Solution:

1
2csharp
3public class Solution {
4    public int MaxAncestorDiff(TreeNode root) {
5        return Dfs(root, root.val, root.val);
6    }
7    
8    private int Dfs(TreeNode node, int minVal, int maxVal) {
9        if (node == null) return maxVal - minVal;
10        minVal = Math.Min(minVal, node.val);
11        maxVal = Math.Max(maxVal, node.val);
12        return Math.Max(Dfs(node.left, minVal, maxVal), Dfs(node.right, minVal, maxVal));
13    }
14}

In the above solutions, we first check if the root is null, and if so, we return 0. Then we initialize min_val and max_val with root's value and call the DFS on it. In the DFS method, for each node, we update min_val and max_val by comparing the current node's value with them. Finally, we return the maximum of differences obtained from the left and right subtree.The time complexity for this approach is O(N), where N is the number of nodes in the tree. This is because each node is visited exactly once.

The space complexity is O(H), where H is the height of the tree. In the worst-case scenario, the height of the tree can be equal to N (in case of a skewed tree). However, in an average case scenario for a balanced binary tree, the height would be logN. The space is used by the implicit function call stack during the recursive DFS calls. This is because, in a depth-first search, the function goes as deep as possible before backtracking, hence the size of the stack can be up to the height of the tree.

The above solutions in Java, Python, JavaScript, C++, and C# correctly and efficiently solve the problem by implementing a depth-first search strategy where they keep track of the minimum and maximum values and calculate the difference at each node of the tree.

In conclusion, these solutions correctly solve the problem by utilising a depth-first search strategy and maintaining the minimum and maximum values seen on the path from the root to a particular node. This approach can also be extended to solve similar problems which involve path comparison in a binary tree.