#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/lowest-common-ancestor-lca

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/lowest-common-ancestor-lca

Lessons

1. Intro

2. What is LCA?

3. Why LCA Matters

Practice Problems

Ready to start learning?

4. Naive Approach - The Idea

5. Naive Approach - Implementation

6. Binary Lifting for LCA

7. Binary Lifting - Preprocessing

8. Key Idea - Binary Search on Ancestors

9. Binary Lifting - Climbing Together

10. Binary Lifting - Complexity

11. Problem - LCA of a Binary Tree

12. Problem - LCA of a Binary Tree - Read Statement

13. Key Idea - Tree to Array

14. Key Idea - Base Cases

15. Algorithm - Recursive LCA

16. Implementation - Recursive LCA

17. Implementation - LCA of a Binary Tree - Implement Solution

18. Walkthrough - Example Tree

19. Lessons - Recursive Tree Traversal

20. Euler Tour for LCA

21. Euler Tour - Construction

22. LCA to RMQ Reduction

23. Sparse Table for RMQ

24. Sparse Table - Building

25. Sparse Table - Querying

26. Euler Tour + RMQ - Full Algorithm

27. Euler Tour + RMQ - Complexity

28. Distance Between Two Nodes

29. Problem - Distance Queries

30. Problem - Distance Queries - Read Statement

31. Key Idea - Precompute Depths and LCA

32. Implementation - Distance Queries

33. Implementation - Distance Queries - Implement Solution

34. Lessons - Amortized Preprocessing

35. Problem - Counting Paths

36. Problem - Counting Paths - Read Statement

37. Key Idea - Path as Range Update

38. Key Idea - Propagating Counts

39. Algorithm - Counting Paths

40. Implementation - Counting Paths

41. Implementation - Counting Paths - Implement Solution

42. Walkthrough - Example

43. Correction - Parent Adjustment

44. Lessons - Difference Arrays on Trees

45. Path Queries Using LCA

46. Weighted Binary Lifting

47. Check Your Understanding

48. Binary Lifting vs Euler Tour

49. Common Mistakes

50. Extensions

51. Section 15 Recap