## Saturday, February 20, 2016

### 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;`
`}`