Diameter of N-Ary Tree
Medium · Graphs · Explanation and code example
Distance with Depth
How it works
Instead of tracking heights (distance down to leaves), we can track depths (distance from root). The diameter through a node equals the sum of the two deepest leaf paths minus twice the current node's depth. This accounts for the path going down to one leaf, back up to the current node, and down to another leaf.
Steps
- Define a recursive function that takes a node and its current depth, returning the maximum depth of any leaf in its subtree.
- For a leaf node, return the current depth.
- For each node, track the two largest depths found among descendants of its children.
- Initialize the first maximum depth with the current depth (handles the case of single-child paths).
- Calculate the diameter through this node as:
max_depth_1 + max_depth_2 - 2 * current_depth. - Update the global diameter if this path is longer.
- Return the maximum depth found to the parent call.
Complexity
- Time complexity:
O(N) - Space complexity:
O(N)
Where
Nis the number of nodes in the tree.
Things to watch for
Only Considering Paths Through the Root
A common mistake is assuming the diameter must pass through the root node. The longest path may be entirely within a subtree. You must track the maximum diameter found at any node, not just the root.
Confusing Height and Depth Definitions
Height (distance down to leaves) and depth (distance from root) are different concepts. Mixing them up leads to incorrect diameter calculations. Height returns the longest path downward from a node, while depth is passed as a parameter representing distance from root.
Only Tracking the Single Maximum Height
To compute the diameter through a node, you need the two largest heights among its children. Tracking only the maximum height misses the second-largest, which is needed for the path length calculation.
Python code example
class Solution:
def diameter(self, root: 'Node') -> int:
diameter = 0
def maxDepth(node, curr_depth):
""" return the maximum depth of leaves nodes
descending from the current node
"""
nonlocal diameter
if len(node.children) == 0:
return curr_depth
# select the top 2 depths from its children
max_depth_1, max_depth_2 = curr_depth, 0
for child in node.children:
depth = maxDepth(child, curr_depth+1)
if depth > max_depth_1:
max_depth_1, max_depth_2 = depth, max_depth_1
elif depth > max_depth_2:
max_depth_2 = depth
# calculate the distance between the two farthest leaves nodes
distance = max_depth_1 + max_depth_2 - 2 * curr_depth
diameter = max(diameter, distance)
return max_depth_1
maxDepth(root, 0)
return diameter
C++ code example
class Solution {
protected:
int bestDiameter = 0;
/**
* return the maximum depth of leaves nodes descending from the given node
*/
int maxDepth(Node* node, int currDepth) {
if (node->children.size() == 0)
return currDepth;
// select the top two largest depths
int maxDepth1 = currDepth, maxDepth2 = 0;
for (Node* child : node->children) {
int depth = maxDepth(child, currDepth + 1);
if (depth > maxDepth1) {
maxDepth2 = maxDepth1;
maxDepth1 = depth;
} else if (depth > maxDepth2) {
maxDepth2 = depth;
}
// calculate the distance between the two farthest leaves nodes.
int distance = maxDepth1 + maxDepth2 - 2 * currDepth;
this->bestDiameter = max(this->bestDiameter, distance);
}
return maxDepth1;
}
public:
int diameter(Node* root) {
this->bestDiameter = 0;
maxDepth(root, 0);
return bestDiameter;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.