Lowest Common Ancestor (LCA)
You've learned binary lifting. Now find the lowest common ancestor of two nodes efficiently.
Lessons
1. Intro
Finding ancestors fast
2. What is LCA?
(Nearest shared ancestor)
3. Why LCA Matters
(Distance and path queries)
4. Naive Approach - The Idea
(Climb to same depth)
5. Naive Approach - Implementation
(Climbing step by step)
6. Binary Lifting for LCA
(Jump in powers of two)
7. Binary Lifting - Preprocessing
(Building the up table)
8. Core Idea - Binary Search on Ancestors
(Finding the split point)
9. Binary Lifting - Climbing Together
(Find the meeting point)
10. Binary Lifting - Complexity
(Preprocessing and query time)
11. Problem - LCA of a Binary Tree
(LeetCode 236)
12. Problem - LCA of a Binary Tree - Read Statement
(LeetCode 236)
13. Core Idea - Multiple Approaches Exist
(enabling array algorithms)
14. Core Idea - Base Cases
(Null and target nodes)
15. Algorithm - Recursive LCA
Combine left and right results
16. Implementation - Recursive LCA
(Pseudocode)
17. Implementation - LCA of a Binary Tree - Implement Solution
(LeetCode 236)
18. Walkthrough - Example Tree
(Tracing the recursion)
19. Lessons - Recursive Tree Traversal
(Bottom-up propagation)
20. Euler Tour for LCA
(Convert tree to array)
21. Euler Tour - Construction
(DFS with recording)
22. LCA to RMQ Reduction
(Minimum depth in range)
23. Sparse Table for RMQ
(Precompute range minimums)
24. Sparse Table - Building
(Dynamic programming)
25. Sparse Table - Querying
(Overlapping ranges trick)
26. Euler Tour + RMQ - Full Algorithm
(Combining both techniques)
27. Euler Tour + RMQ - Complexity
(Time and space analysis)
28. Distance Between Two Nodes
(Using LCA)
29. Problem - Distance Queries
(CSES 1135)
30. Problem - Distance Queries - Read Statement
(CSES 1135)
31. Core Idea - Precompute Depths and LCA
(Setup for fast queries)
32. Implementation - Distance Queries
(Pseudocode)
33. Implementation - Distance Queries - Implement Solution
(CSES 1135)
34. Lessons - Amortized Preprocessing
(Pay once, query many)
35. Problem - Counting Paths
(CSES 1136)
36. Problem - Counting Paths - Read Statement
(CSES 1136)
37. Core Idea - Path as Range Update
Add to endpoints, subtract ...
38. Core Idea - Propagating Counts
(Sum children contributions)
39. Algorithm - Counting Paths
(Mark and propagate)
40. Implementation - Counting Paths
(Pseudocode)
41. Implementation - Counting Paths - Implement Solution
(CSES 1136)
42. Walkthrough - Example
(Tracing the algorithm)
43. Core Insight - Parent Decrement
(Fixing the formula)
44. Lessons - Difference Arrays on Trees
(Efficient path updates)
45. Path Queries Using LCA
(Maximum, minimum, sum)
46. Weighted Binary Lifting
(Carrying extra data)
47. Quiz: LCA Distance
Knowledge check
48. Binary Lifting vs Euler Tour
(When to use each)
49. Common Mistakes
(Pitfalls to avoid)
50. Extensions
(Beyond basic LCA)
51. Section Recap
(What you learned)