Diameter of n ary tree

Tree Depth-First Search

75.4% acceptance

Mar 31, 2026

643

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

Solution

C++

Time O(n)

Space O(n)

LeetCode

solution.cpp

/*
// 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;
  }
};
*/

class Solution {
public:
  int diameter(Node* root) {
    int ans = 0;
    dfs(root, ans);
    return ans;
  }
  
private:
  int dfs(Node* node, int& ans) {
    if (!node) return 0;
    int max1 = 0, max2 = 0;
    for (auto child : node->children) {
      int h = dfs(child, ans);
      if (h > max1) { max2 = max1; max1 = h; }
      else if (h > max2) { max2 = h; }
    }
    ans = max(ans, max1 + max2);
    return max1 + 1;
  }
};