Diameter of N-ary Tree
AmazonThe problem
Given the root of an N-ary tree, compute the length of its diameter.
The diameter is defined as the length of the longest path between any two nodes in the tree. (Nary-Tree input serialization is represented in their level order traversal, with each group of children separated by a null value.)
Input: root = [1,null,3,2,4,null,5,6] Output: 3 **Explanation: **The diameter of the N-ary tree is the longest path between any two nodes, which in this case is 3.
Input: root = [1,null,2,null,3,4,null,5,null,6] Output: 4 Explanation: The diameter of the N-ary tree is the longest path between any two nodes, which in this case is 4.
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]
- The depth of the n-ary tree is less than or equal to 1000.
- The total number of nodes is between [1, 10⁴].
cpp
/**
* Definition for an n-ary tree node.
* class TreeNode {
* public:
* int val;
* vector<TreeNode*> children;
*
* TreeNode() {}
*
* TreeNode(int _val) {
* val = _val;
* }
*
* TreeNode(int _val, vector<TreeNode*> _children) {
* val = _val;
* children = _children;
* }
* };
**/
class Solution {
public:
int diameter(TreeNode* root) {
}
};java
/**
* Definition for an n-ary tree node.
* class TreeNode {
* int val;
* List<TreeNode> children;
*
* TreeNode(int _val) {
* val = _val;
* children = new ArrayList<>();
* }
* }
**/
class Solution {
public int diameter(TreeNode root) {
//Your Code Goes Here
}
}python
"""
# Definition for a Node.
class TreeNode(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution():
def diameter(self, root):
"""
:type root: 'Node'
:rtype: int
"""
#Your Code Goes Herejavascript
/**
* Definition for an n-ary tree node.
* class TreeNode {
* constructor(val) {
* this.val = val;
* this.children = [];
* }
* }
**/
class Solution {
diameter(root) {
}
}csharp
/**
* Definition for an n-ary tree node.
* public class TreeNode {
* public int val;
* public List<TreeNode> children;
* public TreeNode() {}
* public TreeNode(int val) { this.val = val; }
* public TreeNode(int val, List<TreeNode> children) {
* this.val = val;
* this.children = children;
* }
* }
*/
public class Solution
{
public int diameter(TreeNode root)
{
//Your Code Goes Here
}
}go
func diameter(root *TreeNode) int {
}Stuck? Show a way to structure it+
- 01DFS returns the maximum downward height from each node.
- 02Track the largest and second-largest child heights.
- 03Update the global diameter with their sum.
- 04Return one plus the largest child height.
Reference answer
Then expect these follow-ups
How would you reconstruct the diameter path, not only its length?
Tests: parent tracking
How would you avoid recursion-depth limits?
Tests: iterative traversal
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question