General Tree Diameter

Table of Contents

• 2246. Longest Path With Different Adjacent Characters (Hard)
• 3203. Find Minimum Diameter After Merging Two Trees (Hard)
• 1617. Count Subtrees With Max Distance Between Cities (Hard)
• 2538. Difference Between Maximum and Minimum Price Sum (Hard)
• 1245. Tree Diameter (Medium) 👑
• 3313. Find the Last Marked Nodes in Tree (Hard) 👑

2246. Longest Path With Different Adjacent Characters

• LeetCode | LeetCode CH (Hard)

• Tags: array, string, tree, depth first search, graph, topological sort

3203. Find Minimum Diameter After Merging Two Trees

• LeetCode | LeetCode CH (Hard)

• Tags: tree, depth first search, breadth first search, graph

1617. Count Subtrees With Max Distance Between Cities

• LeetCode | LeetCode CH (Hard)

• Tags: dynamic programming, bit manipulation, tree, enumeration, bitmask

2538. Difference Between Maximum and Minimum Price Sum

• LeetCode | LeetCode CH (Hard)

• Tags: array, dynamic programming, tree, depth first search

1245. Tree Diameter

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, breadth first search, graph, topological sort

1245. Tree Diameter - Python Solution

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

• LeetCode | LeetCode CH (Hard)

• Tags: tree, depth first search

Comments