LC: 1245. Tree Diameter - spiralgo/algorithms GitHub Wiki

1245. Tree Diameter

The Essence:

• In this problem, the given tree is an undirected N-ary tree.
• Let n be some node in this tree is connected to k nodes.
• Of these k nodes, there are k different paths to node n . The sum of the two longest 2 of these paths will give us the diameter of the tree with respect to node n.
• Out of all the relative node diameters, the result should be the maximum after traversing the entire tree.

Details:

The process can be implemented recursively after creating the necessary data structure to represent the graph. While traversing, the parent node needs to be ignored. In a DFS approach, this can be done using a extra variable in the function call. Otherwise, it can also be done using a visited[] or parent[] array.