Algorithm to find longest path in a tree that is smaller than x Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any town to any other town within some time $x$.

There are three paths to consider for each node $v$.


Path to the right subtree of $v$
Path to the left subtree of $v$
Path that goes from the left to the right subtree including $v$


My approach to solving this problem is to use dynamic programming and start at leaf nodes to calculate a travel time $T_l$ for every leaf $l$ and set $T_l = 0$. Then work my way up the tree and compute $T_v = max(T_c + w(v,c))$ for every other node where $c$ are the child nodes of $v$ and check if that value is smaller than the given $x$. This would cover the first two cases and would require us to iterate over every node and edge once which is in $O(V+E)$

Where Im not sure is how to cover the third case, i.e. if I wanted to compute the travel time from one leaf node to another. Is that still possible in linear time and how would I do that?
Your dynamic program is a step in the right direction.
My idea would be to maintain two values for a node v:


$L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases)
$U_v$: and the longest path in the subtree of v (i.e., case 3).


You already gave the formula for $L_v$.
For $U_v$ you take the maximum of $U_l$, $U_r$ and $L_l + w(lv) + w(rv) + L_r$ where $l$ and $r$ are the left and right children of v resp.
The last equation corresponds to the path which is formed by the longest paths to the left and to the right which are then joined.