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.)

diameter-n-tree

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 [0, 10^4].

Hints:
For the node i, calculate the height of each of its children and keep the first and second maximum heights (max1_i , max2_i).
Check all nodes and return max( 2 + max1_i + max2_i ).

C++ Definition of N-ary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
 
    Node() {}
 
    Node(int _val) {
        val = _val;
    }
 
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

Compute the Diameter of a N-ary Tree

Similar to compute the depth of a Binary Tree, we can extend the same algorithm to compute the depth of a N-ary tree. To solve this problem, we also need to remember the top 2 depths for each children. Thus, we can integrate this in the Recursive Depth Function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int diameter(Node* root) {
        depth(root);
        return ans;
    }
    
private:
    int ans = 0;
    
    int depth(Node* root) {
        if (!root) return -1;
        int curDepth = 0;
        int m1 = 0, m2 = 0;
        for (const auto &n: root->children) {
            int d = depth(n);
            curDepth = max(curDepth, d);
            if (d > m1) {
                m2 = m1;
                m1 = d;
            } else if (d > m2) {
                m2 = d;
            }
        }
        ans = max(ans, m1 + m2);
        return curDepth + 1;
    }
};

class Solution {
public:
    int diameter(Node* root) {
        depth(root);
        return ans;
    }
    
private:
    int ans = 0;
    
    int depth(Node* root) {
        if (!root) return -1;
        int curDepth = 0;
        int m1 = 0, m2 = 0;
        for (const auto &n: root->children) {
            int d = depth(n);
            curDepth = max(curDepth, d);
            if (d > m1) {
                m2 = m1;
                m1 = d;
            } else if (d > m2) {
                m2 = d;
            }
        }
        ans = max(ans, m1 + m2);
        return curDepth + 1;
    }
};

The diameter of the N-ary tree is equal to the maxmium value of the sum of the Top 2 depths for each node. The N-ary tree will be visited exactly once and thus the Time complexity is O(N). Due to recursive implementation, the Space requirement is O(N) – the usage of implicit stack. And the N-ary tree may be degraded into a linked list – which means the depth may be exactly N for N nodes.

–EOF (The Ultimate Computing & Technology Blog) —