Skip to content

General Tree Diameter

Table of Contents

2246. Longest Path With Different Adjacent Characters

  • LeetCode | 力扣

  • Tags: Array, String, Tree, Depth First Search, Graph, Topological Sort

3203. Find Minimum Diameter After Merging Two Trees

  • LeetCode | 力扣

  • Tags: Tree, Depth First Search, Breadth First Search, Graph

1617. Count Subtrees With Max Distance Between Cities

  • LeetCode | 力扣

  • Tags: Dynamic Programming, Bit Manipulation, Tree, Enumeration, Bitmask

2538. Difference Between Maximum and Minimum Price Sum

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Tree, Depth First Search

1245. Tree Diameter 👑

  • LeetCode | 力扣

  • Tags: Tree, Depth First Search, Breadth First Search, Graph, Topological Sort

from collections import defaultdict, deque
from typing import List


# Tree Diameter
def treeDiameter(edges: List[List[int]]) -> int:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = {0}
    q = deque([0])
    cur = 0

    while q:
        size = len(q)
        for _ in range(size):
            cur = q.popleft()
            for nxt in graph[cur]:
                if nxt not in visited:
                    q.append(nxt)
                    visited.add(nxt)

    visited = {cur}
    q = deque([cur])
    res = -1

    while q:
        size = len(q)
        for _ in range(size):
            cur = q.popleft()
            for nxt in graph[cur]:
                if nxt not in visited:
                    q.append(nxt)
                    visited.add(nxt)
        res += 1

    return res


edges = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]]
assert treeDiameter(edges) == 4

3313. Find the Last Marked Nodes in Tree 👑