Graph Theory37 sections · 1633 units
Open in Course

Combining Paths from Children

Pick two best branches

To maximize a path through node vv, pick the two best downward paths from different children. If vv has children with max downward paths p1,p2,l,pkp_1, p_2, l\dots, p_k, the best path through vv is v+p1+p2v + p_1 + p_2 where p1p_1 and p2p_2 are the two largest.

You cannot use the same child twice. A path visits each node at most once. This constraint forces you to pick two different child subtrees. In a binary tree, you have at most two children, making the choice simple.