findLowestCommonAncestor method

Implementation

Node? findLowestCommonAncestor(Node first, Node second) {
  if (first == second) return first;

  // Получаем глубины узлов для оптимизации
  final depths = getDepths();
  final firstDepth = depths[first] ?? 0;
  final secondDepth = depths[second] ?? 0;

  // Поднимаем более глубокий узел до уровня менее глубокого
  var currentFirst = first;
  var currentSecond = second;

  // Выравниваем глубину узлов
  for (var i = 0; i < (firstDepth - secondDepth); i++) {
    final parent = getNodeParent(currentFirst);
    if (parent == null) return null;
    currentFirst = parent;
  }

  for (var i = 0; i < (secondDepth - firstDepth); i++) {
    final parent = getNodeParent(currentSecond);
    if (parent == null) return null;
    currentSecond = parent;
  }

  // Если после выравнивания узлы совпали - это и есть LCA
  if (currentFirst == currentSecond) return currentFirst;

  // Поднимаемся по дереву, пока не найдем общего предка
  while (currentFirst != root && currentSecond != root) {
    final parentFirst = getNodeParent(currentFirst);
    final parentSecond = getNodeParent(currentSecond);

    if (parentFirst == null || parentSecond == null) return null;
    if (parentFirst == parentSecond) return parentFirst;

    currentFirst = parentFirst;
    currentSecond = parentSecond;
  }

  return root;
}