Given a binary tree, find maximum difference between a node and its descendants in it.

Simple solution would be to traverse the tree and and for every node, we find minimum value node in its left and right subtree. If the difference between the node and its descendants is more than maximum difference found so far, we update it. The time complexity of above solution is O(n^{2}).

We can solve this problem in linear time by processing the tree nodes in bottom-up manner by visiting left and right subtree before processing a node. The function returns the minimum value among all nodes in sub-tree rooted at it. So for any node, we can get minimum value in left subtree and right subtree in constant time. We find the maximum difference for every node and if the difference is more than maximum difference found so far, we update it.

Below is C++ implementation of the algorithm:

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 29 30 31 32 33 34 35 36 37 38 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Helper function to find maximum difference between a node and its // descendants in a binary tree int maxDifference(Node* root, int &diff) { // base case: if tree is empty, return infinity if (root == nullptr) return INT_MAX; // recurse for left and right subtree int left = maxDifference(root->left, diff); int right = maxDifference(root->right, diff); // find maximum difference between current node and its descendants int d = root->data - min(left, right); // update the maximum difference found so far if required diff = max(diff, d); // in order for difference to be maximum, the function should return // minimum value among all nodes in sub-tree rooted at it return min(min(left, right), root->data); } // Find maximum difference between a node and its descendants int maxDifference(Node *root) { int diff = INT_MIN; maxDifference(root, diff); return diff; } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply