handbook_codes
handbook_codes copied to clipboard
Chapter 18: LCA method 1
First of all, thank you for your work.
https://github.com/pulkit1joshi/handbook_codes/blob/main/Chapter%2018%3A%20Tree%20Queries/treequeries_lca_method1.1.cpp
The code for LCA Method 1 appears to have a time complexity of $O(N)$ rather than $O(logN)$ — for example, if the tree is skewed.
(The book says that method 1 has a time complexity of $O(logN)$.)
Using dynamic programming, it seems like it should be possible to move up two or more steps when reaching the minimum common ancestor vertex.
Thanks.