hulk_baba's blog

How to find Lowest Common Ancestor (LCA) if I can compute Kth ancestor of any node in O(logK) time ?
By hulk_baba, history, 7 years ago, In English

Hello, all. I was studying properties of the ancestors in the tree and solved a problem of finding the kth ancestor of any node in O(logK) time by pre-computing 2^jth parent of every node in O(NlogN) time. I am curious to know how can I apply this knowledge to find LCA of 2 given nodes efficiently?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

https://acmcairoscience.wordpress.com/2015/04/07/lowest-common-ancestor-finding-of-o-log-n-binary-lifting-method/

^ Take a read, it's short and simple.

→ Reply