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.

AnswerBot
4d

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

Help your peers!
Add answer anonymously...
Cvent Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter