A Lowest Common Ancestor (LCA) Tree Algorithm

Question

My implementation of the lowest common ancestor (LCA) algorithm for my tree data structure. I selected the non-preprocessed (naïve) implementation for this first implementation. Support for any number of input positions (1+) seemed appropriate. The tree is not binary and a node-based implementation. Any aspect of the code posted is fair game for feedback and criticism.

//! @brief Finds the nearest, ancestorial, common element of the positions.
//!
//! @details The lowest common ancestor (LCA) element of two or more elements in
//! a tree is the lowest, deepest element that has both elements as descendants.
//! That is the last, shared ancestor located farthest from the root. The LCA
//! element of a single valid position iterator is that element iterator itself.
//! The LCA element of the single end position iterator is the end iterator
//! similarly, the LCA element of a collection of position iterators one or more
//! of which is the end iterator is the end iterator because there exists no
//! valid LCA element for the collection.
//!
//! @param first Tree iterator to the first element position of the collection
//! to find the LCA.
//!
//! @param positions The optional second and other remaining element iterators
//! of the collection to find the LCA.
//!
//! @return Iterator to the common most ancestorial element of the elements.
//! Returns the `end` iterator if any position is the `end` iterator which is
//! equal to the iterator to the element past the container's last element.
//!
//! @complexity Quadratic in the number of nodes sought from by the height of
//! the tree container.
[[nodiscard]] constexpr auto
lowest_common_ancestor_element(TreeIterator auto first,
                               TreeIterator auto... positions)
{
  if constexpr (sizeof...(positions)) {
    return [](TreeIterator auto first, TreeIterator auto second,
              TreeIterator auto... positions) {
      using iterator_type = decltype(first);

      if (first == second) {
        return lowest_common_ancestor_element(first, positions...);
      }

      if (!first.node) {
        return first;
      }

      if (!second.node) {
        return second;
      }

      auto *first_ancestor = first.node;
      do {
        if (!first_ancestor->parent) {
          return lowest_common_ancestor_element(iterator_type{ first_ancestor },
                                                positions...);
        }

        auto *second_ancestor = second.node;
        while ((second_ancestor = second_ancestor->parent)) {
          if (first_ancestor == second_ancestor) {
            return lowest_common_ancestor_element(
                iterator_type{ first_ancestor }, positions...);
          }
        };
      } while ((first_ancestor = first_ancestor->parent));

      // Unreachable code under nominal use case. Other invalid cases may have
      // returned early. The result of the application of library functions to
      // invalid ranges is undefined per 23.3.1
      // [iterator.requirements.general]/12.
      return iterator_type{};
    }(first, positions...);
  }

  return first;
}

Unclear areas:

• Is my understanding of the complexity O(Ih) correct? Where I is the number of input node and h the tree height, for a quadratic complexity or simplifies to linear complexity in h for O(h)? It seems to be accepted as O(h) for the typical case for two nodes I = 2 but is it applicable here?
• Is this implementation actually recursive in the number of input position?

The code is tested and updated here.

Answer 1

Answers to your questions

• Is my understanding of the complexity \$O(Ih)\$ correct? Where \$I\$ is the number of input node and \$h\$ the tree height, for a quadratic complexity or simplifies to linear complexity in \$h\$ for \$O(h)\$? It seems to be accepted as \$O(h)\$ for the typical case for two nodes \$I = 2\$ but is it applicable here?

It is \$O(Ih)\$. It might be easier to understand by realizing that your algorihm will always first try to find the LCA of the first two nodes, then you want to find the LCA of the result of the first LCA and the next node, and so on until you processed all the nodes. In the limit for a large number of nodes, each time you go to the next node, you need on about \$h\$ steps.

It is definitely not \$O(h)\$ as even with a binary tree you can have \$O(2^h)\$ nodes, and your algorithm potentially has to check every node; consider that it can only stop early if it reached the top; and the top of the tree might not be in the set of nodes you want to get the LCA of, or it might be the last.

For the case of \$I = 2\$, the complexity is \$O(h^2)\$, as your algorithm basically becomes:

for (auto i: parents_of(firsts))
  for (auto j: parents_of(second))
    if (i == j)
      return i;

• Is this implementation actually recursive in the number of input position?

Yes. This is also easy to see; every time you recursively call lowest_common_ancestor_element(), it is with one less parameter.

Reduce the indentation level

Almost right at the start you increase the indentation level by two because of the if constexpr and lambda function. You can avoid this by just overloading lowest_common_ancestor_element(); one overload takes just one parameter, the other takes two or more:

[[nodiscard]] constexpr auto
lowest_common_ancestor_element(TreeIterator auto first)
{
    return first;
}

[[nodiscard]] constexpr auto
lowest_common_ancestor_element(TreeIterator auto first,
                               TreeIterator auto second,
                               TreeIterator auto... positions)
{
  using iterator_type = decltype(first);

  if (first == second) {
    return lowest_common_ancestor_element(first, positions...);
  }

  ...
}

Separate out the case of two nodes

You are trying to do everything in one function. As already shown above, it helps to separate out special cases. The one with only one node is easy. For three or more nodes, you basically do:

[[nodiscard]] constexpr auto
lowest_common_ancestor_element(TreeIterator auto first,
                               TreeIterator auto second,
                               TreeIterator auto third,
                               TreeIterator auto... positions)
{
  auto LCA_of_first_and_second = lowest_common_ancestor_element(first, second);
  return lowest_common_ancestor_element(LCA_of_first_and_second, third, positions...);
}

Then you are left with the case of two nodes, which is where you have the nested loops:

[[nodiscard]] constexpr auto
lowest_common_ancestor_element(TreeIterator auto first,
                               TreeIterator auto second)
{
  if (first == second || !first.node) {
    return first;
  }

  if (!second.node) {
    return second;
  }

  using iterator_type = decltype(first);

  auto *first_ancestor = first.node;
  do {
    if (!first_ancestor->parent) {
      return iterator_type{ first_ancestor };
    }
    auto *second_ancestor = second.node;
    while ((second_ancestor = second_ancestor->parent)) {
      if (first_ancestor == second_ancestor) {
        return iterator_type{ first_ancestor };
       }
    };
  } while ((first_ancestor = first_ancestor->parent));

  return iterator_type{};
}

Have the iterator be able to get its parent

The casting between nodes and iterators could be avoided if a TreeIterator would have a function to return an iterator to the parent of the node. Alternatively, have a different iterator type that iterates over ancestors, so you could actually write loops like for (auto first_ancestor: first.ancestors()).