Find Maximum Difference Between a Node and its Descendants in a Binary Tree

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

 

For example, consider below tree. The maximum difference between a node and its descendants is 8 – 1 = 7

 
maximum difference binary tree

 
 

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:

 

Download   Run Complete Code

 
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

Notify of
avatar
wpDiscuz