1026. Maximum Difference Between Node and Ancestor

Hello, reader 👋🏽 ! Welcome to day 69 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1026. Maximum Difference Between Node and Ancestor.

🤔 Problem Statement

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

• E.g.:

  • [8,3,10,1,6,null,14,null,null,4,7,13] => 7

  • [1,null,2,null,0,3] => 3

💬 Thought Process - Maximum and minimum nodes

• Intuitively, the maximum difference occurs when we have either:

  • minimum ancestor root value and maximum child value

  • maximum ancestor root value and minimum child value

• So, that's what we'll do. At every node in the tree, we will reset the minimum and maximum value we've seen so far.

• Once we have traversed an entire path, we would have the maximum and minimum values along that path and can return the difference.

• At every node, we will calculate the differences in path across left and right subtrees and return the maximum difference of both.

• For e.g. the path from node 8 to node 1, gives a difference of 7.

  

• The path from node 8 to node 4 gives a difference of 5. But since the maximum of the previous difference (7) and the 5 is 7.

  

• Similarly the other paths give the following differences:

  • 5 (from node 8 to 7)

  • 2 (from node 8 to 10)

  • 6 (from 8 to 13)

  • 6 (from 8 to 14)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1670606815527/G3haOsZdP.png align="center")

👩🏽‍💻 Solution - Maximum and minimum nodes

• Below is the code for the approach for calculating the difference of every path using the maximum and minimum nodes along that path.

/**
 * 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 {
    public int maxAncestorDiff(TreeNode root) {
        return maxAncestorDiffHelper(root, root.val, root.val);
    }

    private int maxAncestorDiffHelper(TreeNode root, int max, int min) {
        if(root == null) {
            System.out.println(max + " " + min + " " + Math.abs(max - min));
            return Math.abs(max - min);
        };

        int val = root.val;
        max = Math.max(val, max);
        min = Math.min(val, min);

        int leftMax = maxAncestorDiffHelper(root.left, max, min);
        int rightMax = maxAncestorDiffHelper(root.right, max, min);



        return Math.max(leftMax, rightMax);
    }
}

Time Complexity: O(n)
  - n = number of nodes in the tree 1
Space Complexity: O(n + m)
  - n = number of nodes in the tree 1

• You can find the link to the GitHub repo for this question here: 1026. Maximum Difference Between Node and Ancestor.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!