Problem statement

https://binarysearch.com/problems/Length-of-the-Longest-Path-in-an-N-Ary-Tree/

Solution

Equal to Leetcode 1245 Tree Diameter.

Complexity

Time is O(n), space is O(h).

Code

class Solution:
    def solve(self, edges):
        G = defaultdict(list)
        for x, y in edges:
            G[x] += [y]
            G[y] += [x]
            
        V, self.res = set(), 0
        
        def dfs(node):
            V.add(node)
            maxs = [-1, -1]
            for neib in G[node]:
                if neib in V: continue
                depth = dfs(neib)
                maxs = sorted(maxs + [depth])[-2:]
            self.res = max(self.res, sum(maxs) + 2)
            return maxs[1] + 1
        
        dfs(1)
        return self.res + 1