Problem Statement¶
In this chapter, we deal with a rooted tree and examine the following two problems on this tree.
In this problem, a rooted tree with n vertices is given as input, followed by q queries. In each query, a vertex v and a number h are provided. It is guaranteed that the vertex's height is greater than h, and we are asked to find the ancestor of vertex v located at height h (which is unique).
The Problem of the Lowest Common Ancestor¶
In this problem, a rooted tree with n vertices is given as input, followed by q queries. In each query, two vertices v and u are provided, and we are asked to find the lowest common ancestor (LCA) of these two vertices. The term lowest common ancestor is commonly abbreviated as LCA, which stands for Lowest Common Ansector.
The Relationship Between These Two Problems¶
If we have a solution for the first problem that answers each query in \(O(x)\), we can answer each query of the second problem in \(O(x*lg(n))\).
LCA Consider these two vertices. The ancestors above their height are common, and the lower ancestors differ. Therefore, we can perform a binary search on the height. To check if the ancestor at height x of these two vertices is common, we can obtain the ancestor at height x of both vertices using the first method and compare whether they are identical.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
