# Maximum Difference Between Node and Ancestor

Jan 04, 2020

int maxAncestorDiff(TreeNode* root) {
if (root == nullptr) return -1;
int minVal, maxVal;
return maxAncestorDiff(root, minVal, maxVal);
}
int maxAncestorDiff1(TreeNode *root, int &minVal, int &maxVal) {
if (root == nullptr) return -1;
minVal = maxVal = root->val;

int d = -1, leftMin, leftMax, rightMin, rightMax;

if (root->left) {
int r = maxAncestorDiff(root->left, leftMin, leftMax);
d = max(r, max(abs(root->val - leftMin), abs(root->val - leftMax)));
minVal = min(minVal, leftMin);
maxVal = max(maxVal, leftMax);
}
if (root->right) {
int r = maxAncestorDiff(root->right, rightMin, rightMax);
d = max(d,max(r, max(abs(root->val - rightMax), abs(root->val - rightMin))));
minVal = min(minVal, rightMin);
maxVal = max(maxVal, rightMax);
}
if (!root->left && !root->right) return -1;
return d;
}


int maxAncestorDiff(TreeNode* root) {
if (root == nullptr) return -1;
int minVal, maxVal;
minVal = maxVal = root->val;
return maxAncestorDiff(root, minVal, maxVal);
}

int maxAncestorDiff(TreeNode *root, int maxVal, int minVal) {
if (root == nullptr) return maxVal - minVal;
maxVal = max(maxVal, root->val);
minVal = min(minVal, root->val);
// cout << maxVal << " " << minVal << endl;
return max(maxAncestorDiff(root->left, maxVal, minVal),
maxAncestorDiff(root->right, maxVal, minVal));
}

LeetCodeLeetCode

Flip Equivalent Binary Trees

All Elements in Two Binary Search Trees