Binary Lifting with k-th ancestor and lowest common ancestor (LCA)

Binary Lifting is a technique used to find the k-th ancestor of any node in a tree in O(logn). This also leads to a faster algorithm in finding the lowest common ancestor (LCA) between two nodes in a tree. It can also be used to compute functions such as minimum, maximum and sum between two nodes of a tree in logarithmic time. The technique requires preprocessing the tree in O(N log N) using dynamic programming.

Read this article to understand Binary Lifting with k-th ancestor and lowest common ancestor (LCA) in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/binary-lifting-k-th-ancestor-lowest-common-ancestor/

In the function findkthancestor()
it should be
currentNode = dp[currentNode][i]
instead of
currentNode = dp[currentNode][2^i]