How should I practice Lowest Common Ancestor in a Rooted Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Karat onsite interview problems in FastPrep.

Is Lowest Common Ancestor in a Rooted Tree associated with Karat?

FastPrep tags this as a Karat onsite interview coding practice problem when the problem catalog has that company and stage context.

Lowest Common Ancestor in a Rooted Tree

Karat● MediumINTERNONSITE INTERVIEW

Learn

Problem statement

Given a rooted tree, return the lowest common ancestor of node IDs a and b: the deepest node that is an ancestor of both queries.

For this exercise, assume root is the root ID and each row of pairs is a distinct relationship [parent,child]. The pairs form one valid general tree rooted at root, with any number of children per node. Pair order does not matter. The represented nodes are the root and every pair endpoint; an empty pair list represents the one-node tree containing only the root.

For this exercise, assume both query IDs are represented, a node is its own ancestor, and equal query IDs are allowed. Return the unique lowest common ancestor as one integer ID. Do not modify the input.

Function

lowestCommonAncestor(root: int, pairs: int[][], a: int, b: int) → int

Examples

Example 1

root = 8pairs = [[8,2],[8,9],[2,5],[2,6]]a = 5b = 6return = 2

This authored general tree gives siblings 5 and 6 the deepest shared ancestor 2.

Example 2

root = 1pairs = [[1,2],[1,3],[1,4],[3,5]]a = 2b = 5return = 1

The queries lie in different root branches, so their lowest common ancestor is 1.

Example 3

root = 7pairs = []a = 7b = 7return = 7

The explicit root represents an authored one-node tree. Under inclusive ancestry, its LCA with itself is 7.

Constraints

For this exercise, assume 1 <= N <= 200 represented nodes and pairs.length = N - 1.
Every pair contains two integer IDs from 0 through 10^6; the root and both queries use that domain.
For this exercise, assume no duplicate edges or cycles, every non-root node has exactly one parent, and every represented node is reachable from the root.