timenomad timenomad - 1 month ago 9
Java Question

Longest path between 2 Nodes

Calculate the longest path between two nodes.

The path is in an arch.

Signature of method is:

public static int longestPath(Node n)


In the example binary tree below, it is 4 (going thru 2-3-13-5-2).



This is what I have right now and for the given tree it just returns 0.

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 && n.getLeftSon() != null && 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 > leftLongestPath ? currNodePath : leftLongestPath;
longestPath = longestPath > rightLongestPath ? longestPath : rightLongestPath;

longestPath(n.getLeftSon(), longestPath);
longestPath(n.getRightSon(), longestPath);

return longestPath > 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;
}


I understand that I'm missing a key concept somewhere... My brain goes crazy when I try tracking the flow of execution...

Am I right by saying that by finding the longest path among the root, its left & right nodes and then recurse on its left & 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...

Answer

Maybe it is just as simple:

public static int longestPath(Node n) {
    if (n != null) {
        return longestPath(n, 0); // forgot return?
    }
    return 0;
}

Its more complicated than one might think at first sight. Consider the following tree:

      1
     / \
    2   3
   / \
  4   5
 / \   \
6   7   8
   / \   \
  9   a   b

In this case, the root node is not even in the longest path (a-7-4-2-5-8-b).

So, what you must do is the following: For each node n you must compute the following:

  • compute longest path in left subtree starting with the root of the left subtree (called L)
  • compute longest path in right subtree starting with the root of the right subtree (called R)
  • compute the longest path in left subtree (not necessarily starting with the root of the left subtree) (called l)
  • compute the longest path in right subtree (not necessarily starting with the root of the right subtree) (called r)

Then, decide, which combination maximizes path length:

  • L+R+2, i.e. going from a subpath in left subtree to current node and from current node through a subpath in right subtree
  • l, i.e. just take the left subtree and exclude the current node (and thus right subtree) from path
  • r, i.e. just take the right subtree and exclude the current node (and thus left subtree) from path

So I would do a little hack and for every node not return just a single int, but a triple of integers containing (L+R+2, l, r). The caller then must decide what to do with this result according to the above rules.