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?