Evil__Coder's blog

Help in trees with minimum depth
By Evil__Coder, history, 5 years ago, In English

If we have to find the tree with minimum depth. Is it a possible solution??

MY Idea

We find the diameter of a tree using two bfs.(First bfs from any node and second bfs from the farthest node in the first bfs). And the minimum depth tree would be the tree with middle element of diameter as root ( or any of the two node if diameter is even ).

Is there any corner cases in this idea?? Or this approach is totally wrong??

Thanks in Advance (:

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Can you please clarify the problem? Do you mean "Given a tree, root it at a vertex so that the depth is minimal"?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes , We have to choose the root such that depth is minimum.

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Im pretty sure its correct, lets start traversing from one end of the diameter to the other one, for the current vertex on the path between the diameter ends the depth of the tree would be the the distance to the farther end of the diameter, if it would be farther than that that means that our diameter isnt actually a diameter because if there is a vertex farther than any of the end of out actual diameter, that means that that should be the diameter instead of the one we found, which is a contradiction, meaning answer for your question can be found on the diameter of the tree, since the depth of the tree rooted on the diameter is equal to the distance to the farther end of the diameter the answer is found on the middle of the diameter

→ Reply