Solution: Tree Diameter

Statement

Given an undirected tree with $n$ nodes labeled from $0$ to $n - 1$, represented by a 2D array edges where $edges.length == n - 1$. Each $edges[i] = [a_i, b_i]$ denotes an undirected edge between nodes $a_i$ and $b_i$. Your task is to return the diameter of the tree.

The diameter of a tree is the number of edges in the longest path between any two nodes.

Constraints:

n $==$ edges.length $+ 1$

edges[i].length = 2

1 $<=$ $n$ $<=$$10^3$

0 $<=$ $a_i, b_i$ $<$ $n$

$a_i$ $\neq b_i$

Solution

The essence of this solution lies in finding the diameter of a tree using graph traversal techniques. A tree is a connected acyclic graph, and its diameter is defined as the longest path between any two nodes.One way to find the diameter is the two-DFS approach:Start DFS from any node to find the farthest node.Perform another DFS from that farthest node to compute the diameter.However, we optimize this by computing the diameter in a single DFS traversal, leveraging the idea that the longest path passing through any node can be determined by summing the two longest distances extending from that node.To determine the longest path, we use the concepts of leaf nodes and parent nodes as in a tree structure. For any parent node, we compute its two longest distances (top1 and top2) to its descendant leaf nodes. The longest path passing through this node is given by:

longest \space path = top1 + top 2

Since any node in the graph can be part of the longest path forming the diameter, we compute the longest paths passing through each node and take the maximum among them as the tree’s diameter. Now, lets look at the below illustration to better understand the above intution.