Problem

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

Examples

Example 1

graph TD
    A(1)
    A --- B(3)
    A --- C(2)
    A --- D(4)
    B(3) --- E(5)
    B(3) --- F(6)
    
    linkStyle 0 stroke:#FF0000,stroke-width:2px;
    linkStyle 1 stroke:#FF0000,stroke-width:2px;
    linkStyle 3 stroke:#FF0000,stroke-width:2px;
  
1
2
3

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

Example 2

graph TD
    A(1) --- B(2)
    B --- C(3) & D(4)
    C --- E(5)
    D --- F(6)

classDef hidden display:none
linkStyle 1 stroke:#FF0000,stroke-width:2px;
linkStyle 2 stroke:#FF0000,stroke-width:2px;
linkStyle 3 stroke:#FF0000,stroke-width:2px;
linkStyle 4 stroke:#FF0000,stroke-width:2px;
  
1
2

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

Example 3

graph TD
    A(1)
    A --- B(2) & C(3) & D(4) & E(5)
    C --- F(6) & G(7)
    D --- H(8) --- L(12)
    G --- K(11) --- N(14)
    E --- I(9) & J(10)
    I --- M(13)

    linkStyle 1 stroke:#FF0000,stroke-width:2px;
    linkStyle 2 stroke:#FF0000,stroke-width:2px;
    linkStyle 5 stroke:#FF0000,stroke-width:2px;
    linkStyle 6 stroke:#FF0000,stroke-width:2px;
    linkStyle 8 stroke:#FF0000,stroke-width:2px;
    linkStyle 9 stroke:#FF0000,stroke-width:2px;
    linkStyle 7 stroke:#FF0000,stroke-width:2px;
  
1
2

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

Similar Problem

Diameter Of a Binary Tree

Solution

Definition of Diameter: The diameter of the tree is the longest path between any two nodes. This path may or may not pass through the root. Hence, we need to compute the longest paths in the subtree of each node.

Method 1 - DFS

We can use a recursive function to traverse through child nodes and calculate the heights.

Here is the approach:

  • Start from the root and recursively calculate the heights of the subtrees of all child nodes.
  • The height of a node is defined as the longest path from the node to any leaf.
  • For each node, calculate the longest two heights among its children (let’s call them h1 and h2).
  • The local diameter at a node will be h1 + h2.
  • Update the global diameter (ans) to be the maximum of the current global diameter and the local diameter.
  1. pick any node u
  2. find the node which is farthest from u, call it x (calculate using the same approach as in Solution 1)
  3. find the node which is farthest from x, call it q (calculate using the same approach as in Solution 1)

The answer will be the length of a path from x to q.

Code

 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
29
30
31
32
33
34
35
36
37
38
39
40
41

class Node {
    public int val;
    public List<Node> children;

    public Node(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

public class Solution {
    int ans = 0;  // Global variable to track the maximum diameter

    public int diameter(Node root) {
        dfs(root);
        return ans;
    }

    private int dfs(Node node) {
        if (node == null) return 0;

        // List to store heights of all child nodes
        List<Integer> heights = new ArrayList<>();
        for (Node child : node.children) {
            heights.add(dfs(child));
        }

        // Sort heights in descending order
        heights.sort(Collections.reverseOrder());
        
        // Get the two largest heights
        int h1 = heights.size() > 0 ? heights.get(0) : 0;
        int h2 = heights.size() > 1 ? heights.get(1) : 0;
        
        // Update the global diameter
        ans = Math.max(ans, h1 + h2);
        
        // Return the height of the current node
        return h1 + 1;
    }
}
 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
29
30

class Node:
    def __init__(self, val: int, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children if children else []

class Solution:
    def diameter(self, root: Optional[Node]) -> int:
        ans = 0  # Global variable to keep track of the maximum diameter

        def dfs(node: Optional[Node]) -> int:
            nonlocal ans  # Access the global `ans` inside this function
            if not node:
                return 0
            
            # Collect heights of all child nodes
            heights = [dfs(child) for child in node.children]
            heights.sort(reverse=True)  # Sort the heights in descending order
            
            # Take the two largest heights for computing the diameter
            h1 = heights[0] if len(heights) > 0 else 0
            h2 = heights[1] if len(heights) > 1 else 0
            
            # Update the global diameter
            ans = max(ans, h1 + h2)
            
            # Return the height of the current node
            return h1 + 1

        dfs(root)  # Start the DFS from the root
        return ans

Complexity

  • ⏰ Time complexity: O(n)
    • Each node of the tree is visited exactly once. Calculating heights and updating the global diameter also takes constant time per node. Hence, the traversal takes O(n).
  • 🧺 Space complexity: O(h)
    • The recursion stack can go as deep as the height h of the tree in the worst case. Therefore, the space complexity is O(h).