How to find the maximum difference between any two nodes in a Binary Tree

0
votes

Can somebody help me in understanding the below algorithm of how to find the maximum difference between any two nodes in a Binary Tree.

http://www.geeksforgeeks.org/maximum-difference-between-node-and-its-ancestor-in-binary-tree/

I'm not understanding why they are trying to get minimum value from left subtree and right subtree when in actual we want max difference & not min difference. So, Shouldn't we be getting the max difference recursively from left & right subtrees & use it to calculate our result?

Thanks in advance !!

2
algorithmdata-structurestreebinary-treebinary-search-tree
Not for any 2 nodes. A is an ancestor of B. – SashaMN
If you want to find the maximum difference of any 2 nodes, just find minimum and maximum. The result will be maximum - minimum. – SashaMN
But the maximum should be an ancestor of the minimum . The answer by @T. Clavarie below , helps. Thanks. – Mayank Mukherjee

2 Answers

0
votes

To find maximum difference it suffices to subtract maximum from minimum. The link you provided is describing algorithm for a different problem: find maximum difference |A-B| where A is ancestor of B.

0
votes

As usual, there are several ways of performing this, and yours might work just as well as the one presented by geeksforgeeks, though it seems harder to implement to me.

The maximum difference between the current node and any other is obtained by substracting the minimum value from the current subtree from the current value. This is why they are taking the minimum value of the right and left subtree. The maximum difference so far is contained in the ref pointer, which is updated if needed.