Graph Theory37 sections · 1633 units
Open in CourseQuiz: LCA via Binary Lifting
Knowledge check
Check Your Understanding
In the LCA algorithm, after equalizing depths you jump both nodes upward in decreasing powers of . Why do you skip a jump when up[u][k] == up[v][k]?
- A.Because you want to stop just below the LCA, not at or above it
- B.Because you have found the LCA at that point
- C.Because equal ancestors mean the nodes share a subtree
- D.Because the table entry is invalid at that level