title: Longest path between 2 Nodes
body: <p>Calculate the longest path between two nodes.<br />
  The path is in an arch.<br />
  Signature of method is: </p>
  
  <pre><code>public static int longestPath(Node n)
  </code></pre>
  
  <p>In the example binary tree below, it is <strong>4</strong> (going thru 2-3-13-5-2).</p>
  
  <p><img src="https://i.stack.imgur.com/qEYyI.jpg" alt=""></p>
  
  <p>This is what I have right now and for the given tree it just returns 0.</p>
  
  <pre><code>public static int longestPath(Node n) {
      if (n != null) {
          longestPath(n, 0);
      }
      return 0;
  }
  private static int longestPath(Node n, int prevNodePath) {
  
      if (n != null &amp;&amp; n.getLeftSon() != null &amp;&amp; n.getRightSon() != null) {
          int currNodePath = countLeftNodes(n.getLeftSon()) + countRightNodes(n.getRightSon());
          int leftLongestPath = countLeftNodes(n.getLeftSon().getLeftSon()) + countRightNodes(n.getLeftSon().getRightSon());
          int rightLongestPath = countLeftNodes(n.getRightSon().getLeftSon()) + countRightNodes(n.getRightSon().getRightSon());
  
          int longestPath = currNodePath &gt; leftLongestPath ? currNodePath : leftLongestPath;
          longestPath = longestPath &gt; rightLongestPath ? longestPath : rightLongestPath;
  
          longestPath(n.getLeftSon(), longestPath);
          longestPath(n.getRightSon(), longestPath);
  
          return longestPath &gt; prevNodePath ? longestPath : prevNodePath;
      }
      return 0;
  }
  private static int countLeftNodes(Node n) {
      if (n != null) {
          return 1+ countLeftNodes(n.getLeftSon());
      }
      return 0;
  }
  private static int countRightNodes(Node n) {
      if (n != null) {
          return 1+ countRightNodes(n.getRightSon());
      }
      return 0;
  }
  </code></pre>
  
  <p>I understand that I'm missing a key concept somewhere... My brain goes crazy when I try tracking the flow of execution...<br />
  Am I right by saying that by finding the longest path among the root, its left &amp; right nodes and then recurse on its left &amp; right nodes passing them the longest path from previous method invocation and finally (when?) return the longest path, I'm not certain as to how you go about returning it...</p>