Depth First Search Algorithm to Find the Largest Difference Between Node and a Descendant in a Binary Tree

Given a binary tree root, return the largest absolute difference between any node and its descendants.

For example, given the following tree:

   0
  / \
 4   2
    / \
   1   7
  / \
 6   3

return 7 since the largest absolute difference is between nodes 7 and 0.

Example 1
Input

1	root = [9, null, [0, null, null]]

root = [9, null, [0, null, null]]

Output
9

Find the Largest Difference Between Node and a Descendant in a Binary Tree using DFS Algorithm

We can perform a Depth First Search Algorithm and pass along the current Maximum and Minimum value in the path from root to the leaf. Then we can update the largest difference by comparing the difference between current node and min/max node.

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

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int largestDifferenceInBinaryTree(Tree* root) {
    if (!root) return 0;
    int ans = 0;
    function<void(Tree*, int, int)> dfs = [&](Tree* root, int curMin, int curMax) {
        if (!root) return;
        ans = max(ans, abs(curMin - root->val));
        ans = max(ans, abs(curMax - root->val));
        if (root->left) 
            dfs(root->left, min(curMin, root->val), 
                max(curMax, root->val));
        if (root->right)
            dfs(root->right, min(curMin, root->val), 
                max(curMax, root->val));
    };
    dfs(root, root->val, root->val);
    return ans;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int largestDifferenceInBinaryTree(Tree* root) {
    if (!root) return 0;
    int ans = 0;
    function<void(Tree*, int, int)> dfs = [&](Tree* root, int curMin, int curMax) {
        if (!root) return;
        ans = max(ans, abs(curMin - root->val));
        ans = max(ans, abs(curMax - root->val));
        if (root->left) 
            dfs(root->left, min(curMin, root->val), 
                max(curMax, root->val));
        if (root->right)
            dfs(root->right, min(curMin, root->val), 
                max(curMax, root->val));
    };
    dfs(root, root->val, root->val);
    return ans;
}

The complexity is O(N) as we need visiting each node in the binary tree exactly once. The space complexity is also O(N) as we are using Recursion which implicitly has O(N) complexity due to stack.

–EOF (The Ultimate Computing & Technology Blog) —