Find the longest path from root to leaf in a tree

Question Detail: 

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.

Asked By : Graviton

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1494

Answered By : Dave Clarke

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.