educative.io

Proof for "We will prune the leaves until we are left with one or two nodes which will be our answer and the roots for MHTs."

Courses
,
#1

How do we can that at max there can be only two nodes in whole graph?

More possible? Can’t think of a case though.

1 Like
#2

Hi @Gaurav7! I think that always you can extend the tree into a straight line with the most separated nodes at the extremes, and the rest of the nodes “hanging”. The middle of this straight line will be the answer, so if its length is even, you take two, but there will never be more than 2.
Hope that view helps you.