Header Ads Widget

Trending

6/recent/ticker-posts

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.