Tree Diameter & Center
Finding tree diameter with two-BFS and DP methods, computing tree center and radius, and solving all-nodes distance queries with rerooting DP.
Lessons
1. Intro
The Goal
2. What is Tree Diameter
Longest possible path
3. Why Diameter Matters
Network analysis applications
4. The Naive Approach
Try all pairs
5. The Two-BFS Trick
Start anywhere, go far twice
6. Why Two-BFS Works
Intuition behind the proof
7. Two-BFS Implementation
Code structure
8. Quiz: Two-BFS Method
Knowledge check
9. CSES 1131 Tree Diameter - Problem Statement
CSES 1131
10. CSES 1131 Tree Diameter - Core Idea
Apply two-BFS directly
11. CSES 1131 Tree Diameter - Algorithm
Step by step
12. CSES 1131 Tree Diameter - Implementation
Pseudocode and code
13. CSES 1131 Tree Diameter - Walkthrough
Example trace
14. CSES 1131 Tree Diameter - Lessons
What you learned
15. The DP Approach
Alternative diameter method
16. DP Method - How It Works
Depth through each node
17. DP Method - Implementation
Recursive DFS
18. Two-BFS vs DP
When to use each
19. Quiz: Diameter Methods
Knowledge check
20. LeetCode 543 Diameter of Binary Tree - Problem Statement
LeetCode 543
21. LeetCode 543 Diameter of Binary Tree - Core Idea
Use DP method
22. LeetCode 543 Diameter of Binary Tree - Algorithm
Recursive DFS
23. LeetCode 543 Diameter of Binary Tree - Implementation
Python solution
24. LeetCode 543 Diameter of Binary Tree - Lessons
summary
25. Tree Center
The most central node
26. Finding the Center
Peeling leaves iteratively
27. Center via Diameter
Middle of longest path
28. Tree Eccentricity and Radius
Measuring centrality
29. Quiz: Tree Center
Knowledge check
30. CSES 1132 Tree Distances I - Problem Statement
CSES 1132
31. CSES 1132 Tree Distances I - Core Idea
Reuse diameter endpoints
32. CSES 1132 Tree Distances I - Algorithm
Three BFS approach
33. CSES 1132 Tree Distances I - Implementation
Pseudocode
34. CSES 1132 Tree Distances I - Walkthrough
Example trace
35. CSES 1132 Tree Distances I - Lessons
core idea
36. CSES 1133 Tree Distances II - Problem Statement
CSES 1133
37. CSES 1133 Tree Distances II - Core Idea
Rerooting DP technique
38. CSES 1133 Tree Distances II - Algorithm
Two-pass DFS
39. CSES 1133 Tree Distances II - Implementation
Python code
40. CSES 1133 Tree Distances II - Walkthrough
Example trace
41. CSES 1133 Tree Distances II - Lessons
Rerooting pattern
42. Quiz: Sum of Distances
Knowledge check
43. Comparing the Problems
Different distance queries
44. Common Mistakes
What to avoid
45. Section Recap
What we learned