Problem statement

https://leetcode.com/problems/fizz-buzz-multithreaded/

Solution

We need to traverse our tree, where dfs(node) will return maximum path, which go from node to any leaf. Using this information we can find diameter: for each node we check two longest paths for its children and take their sum plus 2. In the end we check all longest paths going through all nodes, so we will find our answer.

Complexity

Time complexity is O(n) to traverse our tree: note, that length of maxs will always be not more than 2. Space complexity is O(h).

Code

class Solution:
    def treeDiameter(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(0)
        return self.res