Practice/Google/Leetcode 1522. Diameter of N-Ary Tree

Leetcode 1522. Diameter of N-Ary Tree

CodingMust

Problem

You are given the root of an N-ary tree where each node can have any number of children. Your task is to find the diameter of the tree.

The diameter of a tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of a path is measured by the number of edges between nodes, not the number of nodes.

An N-ary tree is represented using a Node class where each node contains:

• val: an integer value
• children: a list of child nodes (can be empty)

Requirements

1. Calculate the longest path (in edges) between any two nodes in the tree
2. The path can go through any nodes in the tree, not necessarily through the root
3. Handle trees with varying structures (balanced, unbalanced, linear, wide)
4. Return 0 for a single-node tree or empty tree

Constraints

• The number of nodes in the tree is in the range [0, 10^4]
• Each node can have 0 to N children
• Node values are unique integers
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (for recursion stack)

Examples

Example 1:

` Input: 1 / |
2 3 4 / | 5 6

Output: 3 Explanation: The longest path is 5 -> 2 -> 1 -> 4 -> 6, which has 4 nodes and 3 edges. `

Example 2:

` Input: 1 | 2 | 3

Output: 2 Explanation: The path goes from 1 -> 2 -> 3, which contains 2 edges. `

Example 3:

` Input: 1 / |
2 3 4

Output: 2 Explanation: The longest path connects any two leaf nodes through the root (e.g., 2 -> 1 -> 4), which is 2 edges. `