« back

Maximum difference between node and its ancestor

Tags : tree, geeksforgeeks, cpp, medium

Problem Statement - link #

Given a Binary Tree, you need to find the maximum value which you can get by subtracting the value of node B from the value of node A, where A and B are two nodes of the binary tree and A is an ancestor of B.

Your Task: The task is to complete the function maxDiff() which finds the maximum difference between the node and its ancestor.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(h)

Examples #

Example 1:

Input:
      1
    /    \
   2      3
           \
            7
Output: -1
Explanation:The maximum difference we can
get is -1, which is between 1 and 2.

Example 2:

Input:
    5
 /    \
2      1
Output: 4
Explanation:The maximum difference we can
get is 4, which is bewteen 5 and 1.

Constraints #

Solutions #

class Solution {
  public:
    //Function to return the maximum difference between any node and its ancestor.
    int nitish(Node* root, int &res){
        if(!root) return INT_MAX;
        if(!root->left&&!root->right)return root->data;
        int l = nitish(root->left, res);
        int r = nitish(root->right, res);
        int minv = min(l,r);
        res = max(res, root->data-minv);
        return min(minv, root->data);
    }
    int maxDiff(Node* root)
    {
        // Your code here 
        int res = INT_MIN;
        nitish(root, res);
        return res;
    }
};