Is Diameter of N-Ary Tree easy or hard?

Diameter of N-Ary Tree is considered a Medium problem. The challenge is recognizing that the longest path through a node depends on the top two child heights and implementing the DFS efficiently without recomputing subtree heights.

Diameter of N-Ary Tree Python/Java solution

Implement a DFS function that returns the height of each node's subtree. During traversal, maintain the two largest child heights and update a global diameter variable. This pattern works cleanly in Python, Java, C++, and Go using recursion.

How to solve Diameter of N-Ary Tree in O(n)?

Perform a depth-first search and compute subtree heights while traversing. For each node, track the two largest heights among its children. Update a global diameter using their sum, and return the maximum height plus one to the parent.

What is the best approach for Diameter of N-Ary Tree?

The best approach is a single-pass DFS that tracks the two largest child heights at every node. The diameter through a node equals the sum of its two deepest child paths. Updating a global maximum during traversal gives the final diameter in O(n) time with O(h) recursion space.

Is Diameter of N-Ary Tree asked at Google/Amazon/Meta?

Tree diameter problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include binary tree diameter, weighted tree diameter, and general tree longest path questions that test DFS and tree DP patterns.

What data structure is used in Diameter of N-Ary Tree?

The problem uses an N-ary tree structure where each node contains a list of children. The algorithm relies on depth-first search traversal and recursion to compute subtree heights and update the global diameter.

What is the time complexity of Diameter of N-Ary Tree?

The optimal DFS solution runs in O(n) time because each node and edge is visited exactly once. The recursion stack uses O(h) space, where h is the height of the tree. In the worst case of a skewed tree, h can be O(n).

Description Hints 2 Solution Video 9:22

1522. Diameter of N-Ary Tree

Medium75.4% acceptance3 companiesPremium elsewhere, free here

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

Example 2:

Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4

Example 3:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7

Constraints:

The depth of the n-ary tree is less than or equal to 1000.
The total number of nodes is between [1, 10⁴].

Asked at 3 companies

Salesforce Meta Goldman Sachs

Topics

Depth-First Search Tree

Hints open one at a time

Hint 1

For the node i, calculate the height of each of its children and keep the first and second maximum heights (max1_i , max2_i).

Hint 2

Check all nodes and return max( 2 + max1_i + max2_i ).

9:22

Still stuck?Read the written solution, or watch a walkthrough.

Open solution