⚡Flashcard Drill➔
NeetCode #411LC-1522MediumTreesNC Algo100
← Back to All Problems

#411 · #1522 · Diameter of N-Ary Tree(N 叉树的直径)

📌 Problem Statement & Constraints

Given the root of an N-ary tree, return its diameter: the length of the longest path between any two nodes, measured in edges. Constraints: the number of nodes is in [0, 10^4], the depth is at most 1000.

💡 Core Algorithmic Approaches

  1. The same idea as the binary-tree diameter, but a node may have many children.
  2. For each node, track the two largest child depths; the longest path through the node is their sum.
  3. The recursion returns 1 + max(child depths) for the parent to use.
  4. Tracking only the top two depths is what keeps the work linear in the number of children.

💻 Benchmark Python3 Implementation

class Solution:
    def diameter(self, root: "Optional[Node]") -> int:
        self.best = 0

        def depth(node: "Optional[Node]") -> int:
            if not node:
                return 0
            top1 = top2 = 0            # two largest child depths
            for c in node.children:
                d = depth(c)
                if d > top1:
                    top1, top2 = d, top1
                elif d > top2:
                    top2 = d
            # the longest path through this node uses its two deepest subtrees
            self.best = max(self.best, top1 + top2)
            return top1 + 1            # depth for the parent

        depth(root)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once and its children are scanned once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Summing all child depths: only the two deepest matter for the path through a node.
  • Returning top1 + top2 from the recursion: the parent needs a single depth, so the return value is top1 + 1.
  • Measuring in nodes rather than edges: the diameter counts edges, so a leaf contributes 0.
  • Recomputing depths for every node: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems