Hacker News Reader

>I have had to find minimum cost paths in a tree, though.

Umm... every path is a minimum cost path in a tree, because there’s exactly one path between any two vertices.

Non CS people may not understand this at first, but you are exactly right. A 'tree' is connected and has n-1 edges. So there can only be precisely one path between any pair of vertices.

He may have meant a general connected graph (not specifically a tree). In which case, there could be multiple paths and some may be cheaper than others.

That’s a good guess/intuition - you’re correct that it wasn’t a binary tree strictly speaking. It was a situation where each node could activated by conditions on sub nodes, with a cost associated with activating each node. Also, in different scenarios, the tree would come with a different set nodes already activated. So the question was to figure out the minimum cost set of activations and in which order.

It wasn’t a graph though as there was a unique path from the root to each leaf

That’s about as well as I’m going to do here it was a while ago...

Reply on news.ycombinator.com