Binary Tree: Longest path between 2 Nodes

Question

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 1

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.

Answer 2

A correct algorithm is:

1. Run DFS from any node to find the farthest leaf node. Label that node T.
2. Run another DFS to find the farthest node from T.
3. The path you found in step 2 is the longest path in the tree.

This algorithm will definitely work, and you're not limited to just binary trees either. I'm not sure about your algorithm:

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...

because I don't understand what exactly you're describing. Can you work it by hand on an example or try to explain it better? That way you might get better help understanding if it's correct or not.

You seem to be attempting a recursive implementation of basically the same thing just simplified for binary trees. Your code seems rather complicated for this problem however. Check the discussion here for a simpler implementation.

Answer 3

I think You are overcomplicating things.

Think about the longest path that goes through the node n and doesn't go up to the parent of n. What is the relationship between the length of that path and the heights of both subtries connected to n?

After figuring that out, check the tree recursively reasoning like this:

The longest path for a subtree with the root n is the longest path of the following three:

1. The longest path in the subtree, whose root is n.left_child
2. The longest path in the subtree, whose root is n.right_child
3. The longest path, that goes through the node n and doesn't go up to the parent of n

Answer 4

What if, for each node n, your goal was to compute these two numbers:

• f(n): The length of the longest path in the tree rooted at n
• h(n): The height of the tree that is rooted at n.

For each terminal node (nodes having null left and right nodes), it is obvious that f and h are both 0.

Now, the h of each node n is:

• 0 if n.left and n.right are both null
• 1 + h(n.left) if only n.left is non-null
• 1 + h(n.right) if only n.right is non-null
• 1 + max(h(n.left), h(n.right)) if both n.left and n.right are non-null

And f(n) is:

• 0 if n.left and n.right are both null
• max(f(n.left), h(n)) if only n.left is non-null
• ?? if only n.right is non-null
• ?? if both n.left and n.right are non-null

(You need to figure out what replaces the two "??" placeholders. There are choices that make this strategy work. I have tested it personally.)

Then, longestPath(Node n) is just f(n):

public class SO3124566
{
    static class Node
    {
        Node left, right;

        public Node()
        {
            this(null, null);
        }

        public Node(Node left, Node right)
        {
            this.left = left;
            this.right = right;
        }
    }

    static int h(Node n)
    {
        // ...
    }

    static int f(Node n)
    {
        // ...
    }

    public static int longestPath(Node n)
    {
        return f(n);
    }

    public static void main(String[] args)
    {
        { // @phimuemue's example
            Node n6 = new Node(),
                n9 = new Node(),
                a = new Node(),
                n7 = new Node(n9, a),
                n4 = new Node(n6, n7),
                b = new Node(),
                n8 = new Node(null, b),
                n5 = new Node(null, n8),
                n2 = new Node(n4, n5),
                n3 = new Node(),
                n1 = new Node(n2, n3);
            assert(longestPath(n1) == 6);
        }{ // @Daniel Trebbien's example: http://pastebin.org/360444
            Node k = new Node(),
                j = new Node(k, null),
                g = new Node(),
                h = new Node(),
                f = new Node(g, h),
                e = new Node(f, null),
                d = new Node(e, null),
                c = new Node(d, null),
                i = new Node(),
                b = new Node(c, i),
                a = new Node(j, b);
            assert(longestPath(a) == 8);
        }



        assert(false); // just to make sure that assertions are enabled.
            // An `AssertionError` is expected on the previous line only.
    }
}

You should be able to write recursive implementations of f and h to make this code work; however, this solution is horribly inefficient. Its purpose is just to understand the calculation.

To improve the efficiency, you could use memoization or convert this to a non-recursive calculation that uses stack(s).