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/