# 1245. Tree Diameter

Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.

The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, ..., edges.length}.

Example 1:

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: 
A longest path of the tree is the path 1 - 0 - 2.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: 
A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

# Solution

Approach 1: two dfs -- start dfs from a random node, then start dfs on an endpoint of the first dfs.

Approach 2: 1 dfs and along the way, find the sum of top 2 lengths through any node.

# Code (Python)

Approach 1:

    def treeDiameter(self, edges: List[List[int]]) -> int:
        # idea: two dfs -- start dfs from a random node, then start dfs on an endpoint of the first dfs
        neighbors = {i: [] for i in range(len(edges) + 1)}
        for edge in edges:
            neighbors[edge[0]].append(edge[1])
            neighbors[edge[1]].append(edge[0])
        
        def dfs(node, neighbors):
            max_info = (0, node) # (length/steps so far, node)
            stack = [(node, None, 0)]
            while stack:
                node, prev, level = stack.pop()
                if level > max_info[0]:
                    max_info = (level, node)
                for neighbor in neighbors[node]:
                    if neighbor != prev:
                        stack.append((neighbor, node, level + 1))
            return max_info
        
        _, node = dfs(0, neighbors)
        return dfs(node, neighbors)[0]

Approach 2:

    def treeDiameter(self, edges: List[List[int]]) -> int:
        # idea: 1 dfs and find the sum of top 2 lengths through any node
        neighbors = {i: [] for i in range(len(edges) + 1)}
        for edge in edges:
            neighbors[edge[0]].append(edge[1])
            neighbors[edge[1]].append(edge[0])
        
        result = [0] # record sum of top 2 lengths through any node
        self._top_length(0, -1, neighbors, result)
        return result[0]
        
    def _top_length(self, node, parent, neighbors, result):
        top_two = (0, 0) # max 2 lengths starting from this node
        for neighbor in neighbors[node]:
            if neighbor != parent:
                max_length = self._top_length(neighbor, node, neighbors, result)
                if max_length > top_two[0]:
                    top_two = (max_length, top_two[0])
                elif max_length > top_two[1]:
                    top_two = (top_two[0], max_length)
                result[0] = max(result[0], sum(top_two))
        return top_two[0] + 1 # plus 1 for the step from parent to current node
    
    #################################
    # OR not keeping a global variable
        def treeDiameter(self, edges: List[List[int]]) -> int:
        # idea: 1 dfs and find the sum of top 2 lengths through any node
        neighbors = {i: [] for i in range(len(edges) + 1)}
        for edge in edges:
            neighbors[edge[0]].append(edge[1])
            neighbors[edge[1]].append(edge[0])
        
        return self._top_length(0, -1, neighbors)[0]
        
    def _top_length(self, node, parent, neighbors):
        global_max = 0 # sum of top 2 lengths through any node
        top_two = (0, 0) # max 2 lengths starting from this node
        for neighbor in neighbors[node]:
            if neighbor != parent:
                max_seen, max_length = self._top_length(neighbor, node, neighbors)
                if max_length > top_two[0]:
                    top_two = (max_length, top_two[0])
                elif max_length > top_two[1]:
                    top_two = (top_two[0], max_length)
                global_max = max(max_seen, sum(top_two), global_max)
        return global_max, top_two[0] + 1

# Code (C++)

Approach 1:

Approach 2: