Diameter of N-Ary Tree - Solution & Explanation

Problem Overview: Given the root of an N-ary tree, return the diameter of the tree. The diameter is the length of the longest path between any two nodes in the tree. The path may or may not pass through the root, and the length is measured by the number of edges.

Approach 1: Brute Force Height Recalculation (O(n²) time, O(h) space)

A straightforward idea is to treat every node as a potential “center” of the diameter. For each node, compute the heights of all its children and take the two largest heights to form a candidate diameter passing through that node. The problem is that height computation itself requires a recursive traversal of the subtree. If you recompute heights repeatedly for many nodes, the total work becomes O(n²) in the worst case. Space complexity is O(h) for recursion depth, where h is the tree height. This approach works for small trees but scales poorly.

Approach 2: Convert to Graph + Double BFS (O(n) time, O(n) space)

A tree diameter can also be found using two BFS passes. First convert the tree into an undirected graph representation by adding edges between each node and its children. Run BFS from an arbitrary node to find the farthest node A. Then run BFS again from A to find the farthest node from it; the distance between them is the diameter. Each BFS processes every node and edge once, giving O(n) time and O(n) space. This approach is conceptually simple but requires building an adjacency list and queue traversal.

Approach 3: DFS Tracking Top Two Heights (O(n) time, O(h) space)

The optimal solution performs a single depth-first search. For each node, compute the height of its subtree while also updating a global diameter. During DFS, iterate through all children and collect the two largest child heights. If the largest heights are h1 and h2, the longest path passing through the current node is h1 + h2. Update the global maximum with this value. The height returned to the parent is 1 + max(h1, h2, ...), effectively the longest downward path.

Each node is visited exactly once and each child edge is processed once, so the time complexity is O(n). The recursion stack uses O(h) space where h is the height of the tree. This technique is a classic tree DP pattern and appears frequently in diameter-style problems across tree and DFS questions.

Recommended for interviews: The DFS approach that tracks the top two child heights is the expected solution. Interviewers want to see that you recognize the diameter property: the longest path through a node equals the sum of its two deepest child paths. Discussing the brute force idea first shows you understand the definition of diameter, while implementing the single-pass DFS demonstrates algorithmic optimization and clean recursive reasoning.