3 deleted 1 characters in body edited Apr 25 '12 at 7:50 Dave Clarke 17.3k33 gold badges5656 silver badges109109 bronze badges 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'len  This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible. 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. 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. 2 added 3 characters in body edited Apr 25 '12 at 7:49 Raphael♦ 59k2626 gold badges144144 silver badges327327 bronze badges 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 (ppath,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. 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 (p,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. 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. 1 answered Apr 25 '12 at 7:09 Dave Clarke 17.3k33 gold badges5656 silver badges109109 bronze badges 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 (p,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.