Maximum difference between node and its ancestor in Binary Tree - GeeksforGeeks

Maximum difference between node and its ancestor in Binary Tree - GeeksforGeeks
Given a binary tree, we need to find maximum value we can get by subtracting value of node B from value of node A, where A and B are two nodes of the binary tree and A is an ancestor of B. Expected time complexity is O(n).

But among all those differences maximum value is 7 obtained by subtracting 1 from 8, which we need to return as result.

If we are at leaf node then just return its value because it can’t be ancestor of any node. Then at each internal node we will try to get minimum value from left subtree and right subtree and calculate the difference between node value and this minimum value and according to that we will update the result.
As we are calculating minimum value while retuning in recurrence we will check all optimal possibilities (checking node value with minimum subtree value only) of differences and hence calculate the result in one traversal only.

/* Recursive function to calculate maximum ancestor-node

   difference in  binary tree. It updates value at 'res'

   to store the result.  The returned value of this function

   is minimum value in subtree rooted with 't' */

int maxDiffUtil(Node* t, int *res)

{

    /* Returning Maximum int value if node is not

       there (one child case)  */

    if (t == NULL)

        return INT_MAX;

 

    /* If leaf node then just return node's value  */

    if (t->left == NULL && t->right == NULL)

        return t->key;

 

    /* Recursively calling left and right subtree

       for minimum value  */

    int val = min(maxDiffUtil(t->left, res),

                  maxDiffUtil(t->right, res));

 

    /* Updating res if (node value - minimum value

       from subtree) is bigger than res  */

    *res = max(*res, t->key - val);

 

    /* Returning minimum value got so far */

    return min(val, t->key);

}

 

/* This function mainly calls maxDiffUtil() */

int maxDiff(Node *root)

{

    // Initialising result with minimum int value

    int res = INT_MIN;

 

    maxDiffUtil(root, &res);

 

    return res;

}

Read full article from Maximum difference between node and its ancestor in Binary Tree - GeeksforGeeks