Find the longest path from root to leaf in a tree

Question

I have a tree (in the graph theory sense), such as the following example:

This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length assigned to it.

My question is, how to find the longest path starting at the root and ending at any of the leaves? The brute-force approach is to check all the root-leaf paths and taking the one with maximal length, but I would prefer a more efficient algorithm if there is one.

Answer 1

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 LongestPath(node)
   If node is a leaf, return (node,0) 
   If node is not a leaf:  
    For each edge (node,length,next):
       Let (p,l) = LongestPath(next)
       Let (path,len) = (p++[next], l + length)
    Return element (path,len) from previous step with largest value len

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.