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(n2).
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:
// Data structure to store a Binary Tree node
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)
// 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;
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
Thanks for reading.