LeetCode 1522: Diameter of N-Ary Tree Solution

Master LeetCode problem 1522 (Diameter of N-Ary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1522. Diameter of N-Ary Tree

Medium

Tree Depth-First Search

Problem Explanation

Explanation:

To find the diameter of an N-ary tree, we need to calculate the longest path between any two nodes in the tree. This can be achieved by performing a depth-first search (DFS) from the root node to find the maximum depth of the tree. Then, we perform another DFS from the deepest node to find the maximum distance between any two nodes in the tree, which gives us the diameter of the tree.

Algorithm:

Perform a DFS from the root node to find the deepest node in the N-ary tree and calculate the depth of the tree.
Perform another DFS from the deepest node found in step 1 to find the maximum distance between any two nodes.
Return the maximum distance as the diameter of the N-ary tree.

Time Complexity: O(N), where N is the number of nodes in the N-ary tree. Space Complexity: O(N) for the recursive call stack. :

Solution Code

class Solution {
    int diameter = 0;
    
    public int diameter(Node root) {
        if (root == null) return 0;
        
        depth(root);
        
        return diameter;
    }
    
    private int depth(Node node) {
        if (node == null) return 0;
        
        int maxDepth1 = 0, maxDepth2 = 0;
        
        for (Node child : node.children) {
            int currentDepth = depth(child);
            if (currentDepth > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = currentDepth;
            } else if (currentDepth > maxDepth2) {
                maxDepth2 = currentDepth;
            }
        }
        
        diameter = Math.max(diameter, maxDepth1 + maxDepth2);
        
        return 1 + maxDepth1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1522 (Diameter of N-Ary Tree)?

This page provides optimized solutions for LeetCode problem 1522 (Diameter of N-Ary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1522 (Diameter of N-Ary Tree)?

The time complexity for LeetCode 1522 (Diameter of N-Ary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1522 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1522 in Java, C++, or Python.

Back to LeetCode Solutions