0
$\begingroup$

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.

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This looks like it duplicates the first two sentences of David Richerby's answer (which was posted earlier). For future reference, we'd prefer answers that add something new over the existing answers. $\endgroup$
    – D.W. ♦
    Apr 9 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.