Diameter of N-Ary Tree

Diameter of N-Ary Tree

What is this problem about?

The Diameter of N-Ary Tree interview question is the general version of the binary tree diameter problem. You need to find the longest path between any two nodes in a tree where each node can have any number of children.

Why is this asked in interviews?

Goldman Sachs and Meta use this to see if you can generalize a binary tree algorithm. It evaluations your ability to use sorting or selection to find the "Top 2" values among many. It tests whether you can handle iterative child processing within a recursive structure.

Algorithmic pattern used

This uses DFS with a "Top Two" selection logic.

1. At each node, iterate through all its children and calculate their heights.
2. Keep track of the two largest heights among all children.
3. The longest path passing through the current node is the sum of these two largest heights.
4. Update a global maxDiameter.
5. Return largest_height + 1 to the parent.

Example explanation

Node A has children B, C, D.

• B has height 5.
• C has height 8.
• D has height 3.

1. The two largest heights are 8 and 5.
2. Potential diameter at A = $8 + 5 = 13$.
3. Return $8 + 1 = 9$ to A's parent.

Common mistakes candidates make

• Sorting overhead: Sorting all child heights ($O(C \log C)$) when you only need the two largest ($O(C)$).
• Single Child: Not handling nodes with zero or one child correctly (diameter might be just the height of that one child).
• Recursion Depth: Not considering that N-Ary trees can be very shallow but very wide, or very deep.

Interview preparation tip

To find the two largest numbers in a list in $O(N)$, use two variables (max1, max2) and update them as you scan. This is a common sub-task in many "Hard" coding problems.