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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting

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

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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting

Lessons

1. Intro

2. The k-th Ancestor Problem

3. Naive Approach

Practice Problems

Ready to start learning?

4. Binary Representation Key Idea

5. Sparse Table Idea

6. Table Dimensions

7. Base Case - First Column

8. Recurrence Relation

9. Recurrence Example

10. Building the Table

11. Building Code

12. Answering Queries

13. Query Pseudocode

14. Query Example

15. Complexity Summary

16. Problem - Company Queries I

17. Key Idea - Tree Structure

18. Key Idea - Handling Invalid Queries

19. Algorithm

20. Company Queries I - Implementation

21. Walkthrough

22. Lessons Learned

23. Extension - LCA

24. Problem - Company Queries II

25. Key Idea - Same Depth First

26. Key Idea - Binary Search for LCA

27. Why This Works

28. Algorithm

29. Company Queries II - Implementation

30. Walkthrough

31. Walkthrough - Different Subtrees

32. Lessons Learned

33. Problem - Kth Ancestor of a Tree Node

34. Key Idea - Constructor Preprocessing

35. Key Idea - Query Method

36. Algorithm

37. Kth Ancestor - Implementation

38. Walkthrough

39. Lessons Learned

40. Applications Beyond Ancestors

41. Space Improvement Note

42. Comparison to Naive Approach

43. Next Section Teaser

44. Section 14 Recap