lowestCommonAncestor function

int lowestCommonAncestor(
  1. List<int> parent,
  2. int u,
  3. int v
)

Parent array: entry at index i is the parent of node i; root has -1. Audited: 2026-06-12 11:26 EDT

Implementation

int lowestCommonAncestor(List<int> parent, int u, int v) {
  // Record every ancestor of u up to the root (a node is its own ancestor here),
  // following the parent links until -1 signals the root.
  final Set<int> path = <int>{};
  int nodeU = u;
  while (nodeU >= 0) {
    path.add(nodeU);
    nodeU = parent[nodeU];
  }
  // Walk v upward and return the first node already on u's path — by ascending
  // from v, that first hit is the deepest shared ancestor (the LCA). Reaching
  // the root without a match means u and v live in disjoint trees of a forest,
  // reported as -1.
  int nodeV = v;
  while (nodeV >= 0) {
    if (path.contains(nodeV)) return nodeV;
    nodeV = parent[nodeV];
  }
  return -1;
}