Header Ads Widget

Develop Your Creative Skill with
Free Design Tutorials

Our blog helps to Provide Latest Tips and Tricks tutorials about Blogging
Business, SEO Tips, much more. this Blog and stay tuned to this
blog for further updates.

Maximum difference between node and ancestor in Binary Tree

 Problem:- Find Maximum difference between Node and its Ancestor in Binary Tree

We have given a Binary Tree and we have to find the maximum difference between any Node and its Ancestor. 
Let us understand this question with an example, Let A be the value of any Node and B be the value of any Ancestor of A then |A-B| should be Maximum.

Input: Node = [12,0,10,1,4,null,20,null,null,15,7,23]
Output: 15
Input: Node = [2,4,5,8,9,null,0,null,null,12,7,10]                                              Output: 10


In the First Example Maximum Difference between Node and Ancestor is |0-15|=15 and in the second case |0-10|=10.

Maximum difference between node and  ancestor in Binary Tree


Step to find  Maximum difference Between Node and Ancestor in Binary Tree
  • Find the Minimum element of the Left Branch of the Tree.
  • Find the Minimum element of the Right branch of the Tree.
  • Find Same for Right Branch of the tree.
  • Now find the maximum difference between nodes of the two branches.

Here is the Code for the Problem, But I will recommend You to try First this problem at LeetCode and geeks for geeks.

Solution In Java Programming Language 



  public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode() {}
 TreeNode(int val) { this.val = val; }
 TreeNode(int valTreeNode leftTreeNode right)
{
   this.val = val;
   this.left = left;
   this.right = right;
     }
 }
 
class Courpedia {
static int help(TreeNode root,int mxf,int min,int max)
    {
        
if(root==null && root==nullreturn mxf;
int cursum=root.val;
min=Math.min(min,cursum);
max=Math.max(max,cursum);
mxf=Math.max(mxf,max-min);
        
return Math.max(help(root.left,mxf,min,max),help(root.right,mxf,min,max));   
    }
public int maxAncestorDiff(TreeNode root)
{
        
return  help(root,0,root.val,root.val);   
        
    }
}


 The solution in the C++ Programming language


class Solution {
 int diff;
void help(TreeNode* root,int min,int max)
    {if(root == NULL)
      return;
int mi = min(min,root->val);
int ma = max(max,root->val);
diff = max(abs(ma-mi),diff);
help(root->left,mi,ma);
help(root->right,mi,ma);
    }
public:
int maxAncestorDiff(TreeNode* root){
 diff = 0;
help(root,root->val,root->val);
        return diff;
        
    }
};
Time Complexity= O(N)

In all the questions of Binary Tree, you should have a strong catch on Recursion and BackTracking. In our solution, we recursively iterated through all the Nodes of the Tree to find the maximum difference between Node and Ancestor.