LCA Problem Series
LCA ①) Linear LCA query</span
LCA ②) LCA query using Sparse Table
LCA ③) LCA query using Segment Tree
LCA ④) LCA reducted RMQ

1. Problem

  • Input: a rooted tree $T$ of $n$ nodes two nodes $u$, $v$ in $T$

  • Output: the least common ancestor of $u$, $v$

fig 1. LCA problem

  The Least Common Ancestor(LCA) is the well-know problem. LCA is the node furthest from the root that is an ancestor of both given nodes $u$ and $v$. The notation of LCA query of nodes $u$ and $v$ of $T$ is $LCA_T(u,v)$. In this problem, the ancestor of node $v$ includes $v$. For example, in figure 1, $LCA_T(7, 9)$ is node $4$. And, $LCA_T(2,6)$ is node $2$, because ancestor of node $2$ includes node $2$.



2. Naive solution

  In this post, I introduce naive solution of LCA problem. It is very simple and intuitive.

fig 2. The outline of naive solution

  1. If $u$ is the node whose depth is greater than another, go up by checking one node at a time toward the root until the depth is the same as the depth of the other nodes. Change $u$ to the found ancestor whose depth is same with the depth of $v$.
  2. Go up one node at a time from node $u$ and $v$ toward the root. And, check whether the currently checked ancestor nodes of $u$ and $v$ are same.

  We can find LCA of &u& and &v& in both the first procedure and the second procedure.



3. Complexity

  • Time Complexity:
    • query time: $O(n)$
  • Space Complexity: $O(1)$

  There is no more space used. In the worst case, if $T$ is a skewed tree, both procedures runs in $O(N)$ time.

Refers

Crocus, “LCA(Lowest Common Ancestor) 알고리즘”



Next: LCA ②) LCA query using Sparse Table