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
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 val, TreeNode left, TreeNode 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==null) return 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 the Node and Ancestor.
