hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Maximum Difference Between Node and Ancestor


  • Approach:

    1. As said maximum distance between ancestor nodes. So to find the maximum distance, we need to find two values those are Maximum and Minimum in a subtree from the root

    2. I did the same. While traversing through the tree, I remembered the Maximum value I found using the MaxSofar variable.

    3. Did the same for remembering the Minimum value I found using the MinSofar variable.

    4. Later when I reached the end of the tree, returned the distance so far we found from MaxSofar and MinSofar variables.

    5. Along with, calculating the maximum among the values and returning the final value.


  • Time and Space Complexity:

    • Time Complexity: O(N)

    • Space Complexity: O(1) + Auxilary Stack.


Code [C++]

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int maxAncestorDiff(TreeNode* root, int MaxSofar = -1, int MinSofar = 100001) {

if(!root){

return abs(MaxSofar - MinSofar);

}

int ans = 0;

ans = max(ans, maxAncestorDiff(root->left, max(MaxSofar, root->val), min(MinSofar, root->val)));

ans = max(ans, maxAncestorDiff(root->right, max(MaxSofar, root->val), min(MinSofar, root->val)));

return ans;

}

};