FastPrepLowest Common Ancestor with a Changing Root
Problems/Lowest Common Ancestor with a Changing Root

Lowest Common Ancestor with a Changing Root

Infosys logoInfosys● HardFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a thread about the Infosys SP/DSE exam, a commenter listed this as Q2 and gave the full task: a tree, and queries that each choose a root and two nodes and ask for their lowest common ancestor under that root.

No limits or examples were given. This version adds limits, counts a node as its own ancestor, and returns all answers as one array.

The judged task matches the report at about 95%.

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^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= a, b <= n and a != b
  • The edges form one tree that connects all n nodes.
  • 1 <= queries.length <= 2000
  • queries[j].length == 3
  • 1 <= 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
All Infosys interview questionsSee Infosys hiring insights
Saved
class Solution {
    public int[] lcaWithRoot(int n, int[][] edges, int[][] queries) {
        // Write your code here.
    }
}
Checking account…