Tree Diameter — LeetCode 1245 Python Solution
MediumLeetCode PremiumTreeDepth-First SearchBreadth-First SearchGraphTopological Sort
- Problem
- #1245
- Pattern
- Topological Sort
- Reading time
- 3 min
- Source
- leetcode.com
The problem
The diameter of a tree is the number of edges in the longest path in that tree. There is an undirected tree of n nodes labeled from 0 to n - 1.
Example
- Input
- edges = [[0,1],[0,2]]
- Output
- 2
- Explanation
- The longest path of the tree is the path 1 - 0 - 2.
Python solution
Python
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
def dfs(i: int, fa: int, t: int):
for j in g[i]:
if j != fa:
dfs(j, i, t + 1)
nonlocal ans, a
if ans < t:
ans = t
a = i
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = a = 0
dfs(0, -1, 0)
dfs(a, -1, 0)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Topological Sort
Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1245. Tree Diameter is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.
The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1245. Tree Diameter?
- LeetCode 1245. Tree Diameter is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1245. Tree Diameter?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1245. Tree Diameter?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1245. Tree Diameter cover?
- LeetCode 1245. Tree Diameter is tagged Tree, Depth-First Search, Breadth-First Search, Graph and Topological Sort on LeetCode.
- Is LeetCode 1245. Tree Diameter a premium problem?
- Yes. LeetCode 1245. Tree Diameter is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.