Lowest Common Ancestor with a Changing Root
Updated
Problem statement
You are given an undirected tree with n nodes, numbered from 1 to n. edges[i] = [a, b] means nodes a and b are joined by an edge.
You are also given queries. Each query is [r, u, v]. For that query only, hang the tree from node r, so r is the root. Then find the lowest common ancestor of u and v: the node farthest from r that lies on the path from r to u and also on the path from r to v. A node counts as its own ancestor, so the answer can be u, v, or r itself.
The queries are independent: the root of one query does not change the next one. Return an array whose j-th value is the answer to queries[j].
Function
lcaWithRoot(n: int, edges: int[][], queries: int[][]) → int[]Examples
Example 1
n = 6edges = [[1,2],[1,3],[2,4],[2,5],[3,6]]queries = [[1,4,5],[4,5,6],[6,4,3]]return = [2,2,3]Query [1, 4, 5]: with root 1, nodes 4 and 5 both hang under 2, so the answer is 2.
Query [4, 5, 6]: with root 4, the path to 5 is 4 → 2 → 5 and the path to 6 is 4 → 2 → 1 → 3 → 6. They split at 2.
Query [6, 4, 3]: with root 6, the path to 3 is 6 → 3 and the path to 4 is 6 → 3 → 1 → 2 → 4. Node 3 is on both, and it is the farthest such node from the root.
Example 2
n = 4edges = [[1,2],[2,3],[3,4]]queries = [[3,1,4],[1,4,4],[4,1,2]]return = [3,4,2]The tree is the line 1 - 2 - 3 - 4.
Query [3, 1, 4]: root 3 sits between 1 and 4, so the two paths share only 3.
Query [1, 4, 4]: both nodes are 4, and a node is its own ancestor, so the answer is 4.
Query [4, 1, 2]: with root 4, the path to 1 is 4 → 3 → 2 → 1, which passes 2, so the answer is 2.
Example 3
n = 1edges = []queries = [[1,1,1]]return = [1]The tree has one node, so every query answers 1.
Constraints
1 <= n <= 2 * 10^4edges.length == n - 1edges[i].length == 21 <= a, b <= nanda != b- The edges form one tree that connects all
nnodes. 1 <= queries.length <= 2000queries[j].length == 31 <= r, u, v <= n
More Infosys Online Assessment questions
- Minimum Leaf Path Sum over All RootsOA · Seen Nov 2026
- Split Array to Minimize the Largest SumOA · Seen Nov 2026
- Cherry PickupOA · Seen Nov 2026
- Lexicographically Smallest Grid Path with One Letter ChangeOA · Seen Nov 2026
- Minimum Cost to Supply Water with Wells and PipesOA · Seen Nov 2026
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3OA · Seen Nov 2026
- Minimum Rounds to Complete All TasksOA · Seen Nov 2026
- Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
- Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
- Usable Water with Contaminated PillarsOA · Seen Oct 2026
Similar questions at other companies
- Minimum Tree Diameter After Removing K LeavesMathWorks · OAMathWorks interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Thread Count (Also for Infra Automation Intern)Snowflake · OASnowflake interview questions
- Tree Pythagorean TriplesIBM · OAIBM interview questions
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Longest Transfer Time in a Server TreeRippling · OARippling interview questions
- Distance Between Two Tree NodesAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Binary Tree Nodes at Distance KApple · ONSITE INTERVIEWApple interview questions
- Find the Tree DiameterAdyen · ONSITE INTERVIEWAdyen interview questions