1026. Maximum Difference Between Node and Ancestor

Maximum Difference Between Node and Ancestor

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

 

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

Approach) Recursion

var maxAncestorDiff = function(root) {
    if(root == null) { return 0; }
	
    let result = 0;
    helper(root, root.val, root.val);
    
    function helper(root, max, min) {
        if(root == null) {
            result = Math.max(result, max-min);
            return;
        }
        
        max = Math.max(max, root.val);
        min = Math.min(min, root.val);
        
        helper(root.left, max, min);
        helper(root.right, max, min);
    }

    return result;
};

Approach) Depth First Search

var maxAncestorDiff = function(root) {
    
    function traverse(node, max, min) {
        if(!node) return max - min; 
        
        max = Math.max(max, node.val);
        min = Math.min(min, node.val);
        
        return Math.max(
            traverse(node.left, max, min),
            traverse(node.right, max, min)
        )
    }
    return traverse(root, root.val, root.val);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 1026. Maximum Difference Between Node and AncestorI hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!