title: Two nodes at the maximum distance in a binary tree
body: <p>I am stuck up with a modified version of the problem ( Find two nodes located at a distance k in a binary tree). </p>
  
  <p>I was trying to define the distance between two nodes and I believe that it is the minimum number of nodes needed to travel from node n1 to node n2 along the tree branches.</p>
  
  <p>Well proceeding with this assumption, I arrived at a situation where I believe I need to know for each node if it is to the left or right of the root.</p>
  
  <p>Case1 : If n1 and n2 are on different side then I climb to the root ( distance equals to depth of the node n1 - assuming n1 is on left) and then I run down to the right node n2 ( distance equals to the depth of n2). So the maximum distance between two nodes n1 , n2 is the sum of their depths if they are on different sides of the root.</p>
  
  <p>Case 2 : If n1 and n2 are on the same side, I find an ancestor common to both in the tree hierarchy and repeat the same process considering the ancestor a root as I did in the case 1.
  The minimum distance will be the sum of their depths from root - 2 times the depth of common ancestor.</p>
  
  <p>Now, the problem with this is, I end up doing this for every pair of node bluntly. I can optimize it to not check a pair if I know a pair of node which are at a distance more than this but how?</p>
  
  <p>Please suggest the rest of the solution.</p>