Is there an efficient way to find a path from root to a leaf such that it has the maximum sum of degrees of nodes from all the paths possible in the tree.
For example if a tree is defined as the one in which each node is an integer and it has as many child nodes as the perfect divisors of the integer. And the root node is 16 then the sum of degrees of the required path would be 4+4+3+2+1 = 14. The path being : 16->8->4->2->1.
In a tree, there is exactly one path from the root to any vertex. So just do depth- or breadth-first search on the tree and label each vertex with the sum of the degrees on the path from the root to there. Then pick the leaf with the smallest value.
An optimization could be to use greedy best-first search, where you maintain a queue of vertices in increasing order of their weight (sum of degrees on the path from the root). The first leaf you find would then be guaranteed to be the one of minimal weight. This would reduce the number of vertices that you look at but it's possible that the additional overhead of maintaining the priority queue would negate that benefit.
In a tree, there is only one path between the root and any leaf so you can just do a Depth-First Search and get the desired result.
