Lowest Common Ancestor (LCA) Problem Statement
Understanding the concept of Lowest Common Ancestor (LCA) in graph theory and computer science is essential.
Consider a rooted tree ‘T’ containing ‘N’ nodes. The LCA between two nodes, ‘u’ and ‘v’, is the lowest node in the tree ‘T’ such that both ‘u’ and ‘v’ are descendants of this node (permitting a node to be its own descendant).
As an illustration, in a given tree, the LCA of nodes 5 and 8 is node 2, since node 2 lies on the path from node 5 to the root (node 1) and from node 8 to the root (node 1).
Example:
Input:
T = 1
N = 8
Edges: (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (6, 8)
Q = 2
Queries: (5, 8), (4, 6)
Output:
2
1
Explanation:
- For nodes 5 and 8, the paths to the root are 5 → 2 → 1 and 8 → 6 → 3 → 1 respectively; LCA is 2.
- For nodes 4 and 6, paths are 4 → 2 → 1 and 6 → 3 → 1; LCA is 1.
Constraints:
1 <= T ≤ 5
1 <= N ≤ 105
1 <= Q ≤ 105
1 <= u, v ≤ N
- Time Limit: 1 sec
Note:
For each test case, the tree is rooted at node 1.
The Lowest Common Ancestor (LCA) problem involves finding the lowest node in a tree that is an ancestor of two given nodes.
LCA is the lowest node in a tree that is an ancestor of both given nodes.
The ...read more
Top Cvent Software Developer interview questions & answers
Popular interview questions of Software Developer
Reviews
Interviews
Salaries
Users/Month