-2
$\begingroup$

Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1<= n <=100000.

E.g. enter image description here

For Above tree answer would be A,B,F,G

I tried the O(n2) approach (Running Dfs from each node) but need a solution better than it.

$\endgroup$
4
  • 1
    $\begingroup$ So what is your question? What did you try and where did you get stuck? What are your requirements for the solution? $\endgroup$
    – Juho
    Commented Oct 3, 2021 at 14:34
  • $\begingroup$ I need solution better than O(N2) $\endgroup$ Commented Oct 3, 2021 at 14:47
  • 3
    $\begingroup$ OK. What about the rest of my questions? I encourage you to add all these details into your question for otherwise it will likely be closed. $\endgroup$
    – Juho
    Commented Oct 3, 2021 at 14:54
  • 1
    $\begingroup$ It is great that a picture is included in the question. A usual step to try next is to see if you can observe something and then check whether that something could be useful. $\endgroup$
    – John L.
    Commented Oct 7, 2021 at 19:32

1 Answer 1

2
$\begingroup$

One-line takeaway: a tree has either one center or two adjacent centers, which are shared by all diameters.


The clue to solve the problem faster is sort of hidden in the symmetric tree given in the question. You can observe that the node D is the center of the tree. Every endpoint of a diameter is 2 edges away from D.

However, all trees are not symmetric. For example, we can remove node B from the given graph. Well, node D remains to be "the center".

In general, if a diameter of a tree is of even length, that diameter has a node at its center. For example, the diameter
$\quad\quad$ A - C - D - E - G $\quad\quad$
has node D as its center node. Moreover, that center node is the center node of every diameter of the tree. So in this case, we can locate the center. Then breadth-first (level-by-level) search starting from the center. The nodes we will visit at the furthest level will be all endpoints of all diameters.

Another case is when diameters are of odd length. Then each diameter has two nodes in the middle. For example, imagine node F and G are removed. Then node C and D are the center nodes. Moreover, those two center nodes are the centers nodes of every diameter of the tree. In this case, we will locate the centers. Imagine the edge between the two centers is broken. Then we can do two breadth-first (level-by-level) search, each time starting from one of the two centers. The nodes we will visit at the furthest level in either BFS will be all endpoints of all diameters.

Let $n$ be the number of nodes in the tree.

  • It takes $O(n)$ time to find a diameter, either by one DFS or two DFS.
  • It takes $O(n)$ time to locate the center or centers of a diameter.
  • One BFS in the case of one center or Two BFS in the case of the two centers will find all the endpoints of diameters. This takes $O(n)$ time. (Instead, we could also do one DFS, keeping track of the distance and, in the case of two centers, which side of center the node is in. This also takes $O(n)$ time.)

So, the whole algorithm takes $O(n)$ time.


Exercise. Show that all diameters of a tree share their centers, whether there is one center or two centers.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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