We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Diameter of N-Ary Tree

Number: 1665

Difficulty: Medium

Paid? Yes

Companies: Meta, DoorDash

Problem Description

Given the root of an N-ary tree, compute the length of the diameter of the tree. The diameter is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The input is provided as a level order traversal where each group of children is separated by a null value.

Key Insights

  • The diameter of the tree can be found by considering the two largest depths from any node among its children.
  • Use a depth-first search (DFS) to compute the maximum depth from each node.
  • For each node, the potential diameter is the sum of the two longest depths among its children.
  • Update a global variable tracking the maximum diameter as you recurse through the tree.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack (worst-case O(n) for a skewed tree).

Solution

Use a DFS approach to traverse the tree. At each node, calculate the longest and second longest depth among its children. The sum of these two depths gives the candidate diameter through that node. Maintain a global variable to track the maximum diameter found so far. Return the maximum depth from the node (i.e., one plus the largest depth among its children) to be used in parent's calculations.

Code Solutions

# Definition for a Node.
# class Node:
#     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: 'Node') -> int:
        # Global variable to keep track of the maximum diameter found so far.
        self.max_diameter = 0
        
        def dfs(node):
            if not node:
                return 0  # Base case: if the node is None, return depth 0
            
            # Variables to hold the top two maximum depths from the children.
            max_depth1, max_depth2 = 0, 0
            
            # Iterate over each child to compute their maximum depths.
            for child in node.children:
                child_depth = dfs(child)  # Recurse on the child
                # Update the two largest depths
                if child_depth > max_depth1:
                    max_depth2 = max_depth1
                    max_depth1 = child_depth
                elif child_depth > max_depth2:
                    max_depth2 = child_depth
            
            # Update the maximum diameter. The candidate is the sum of the two deepest paths.
            self.max_diameter = max(self.max_diameter, max_depth1 + max_depth2)
            
            # Return the maximum depth from this node.
            return max_depth1 + 1
        
        dfs(root)
        return self.max_diameter
← Back to All Questions