Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val – B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Binary tree

Example 1:
Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
We have various ancestor-node differences, some of which are given below :
|8 – 3| = 5
|3 – 7| = 4
|8 – 1| = 7
|10 – 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 – 1| = 7.

Note:
The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

Depth First Search Algorithm to Find the Maximum Difference Between Node and Ancestor of a Given Binary Tree

We can utilise a helper function which pass down the min and max value for the current sub tree. Then, at any time, we can update the answer by storing the maximum of (max – min).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        if (root == nullptr) return 0;
        dfs(root, root->val, root->val);
        return ans;
    }
private:
    int ans = 0;
    void dfs(TreeNode* root, int small, int big) {
        if (root == nullptr) return;
        big = max(big, root->val);
        small = min(small, root->val);
        int cur = big - small;
        ans = max(ans, cur);
        dfs(root->left, small, big);
        dfs(root->right, small, big);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        if (root == nullptr) return 0;
        dfs(root, root->val, root->val);
        return ans;
    }
private:
    int ans = 0;
    void dfs(TreeNode* root, int small, int big) {
        if (root == nullptr) return;
        big = max(big, root->val);
        small = min(small, root->val);
        int cur = big - small;
        ans = max(ans, cur);
        dfs(root->left, small, big);
        dfs(root->right, small, big);
    }
};

The above C++ code implements the Depth First Search Algorithm in Recursion fashion. And the answer is stored globally. It can be also passed as a reference parameter.

The algorithm runs at O(N) complexity in both time and space where N is the number of nodes in the binary tree. We can however, make the recursive DFS function return the result for the subtree, thus, making the code a little bit concise and easy to understand/follow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        if (root == nullptr) return 0;
        return dfs(root, root->val, root->val);
    }
private:
    int dfs(TreeNode* root, int small, int big) {
        if (root == nullptr) return big - small;
        big = max(big, root->val);
        small = min(small, root->val);
        return max(dfs(root->left, small, big),
                   dfs(root->right, small, big));
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        if (root == nullptr) return 0;
        return dfs(root, root->val, root->val);
    }
private:
    int dfs(TreeNode* root, int small, int big) {
        if (root == nullptr) return big - small;
        big = max(big, root->val);
        small = min(small, root->val);
        return max(dfs(root->left, small, big),
                   dfs(root->right, small, big));
    }
};

The terminating condition for the recursive helper function is the difference value between the min and max value that is passed TOP-down from the root of the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —