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.

Implementation

int lowestCommonAncestor(List<int> parent, int u, int v) {
  final Set<int> path = <int>{};
  int nodeU = u;
  while (nodeU >= 0) {
    path.add(nodeU);
    nodeU = parent[nodeU];
  }
  int nodeV = v;
  while (nodeV >= 0) {
    if (path.contains(nodeV)) return nodeV;
    nodeV = parent[nodeV];
  }
  return -1;
}