Lowest common ancestor of two leaves in a tree

Question

I have the following tree structure:

struct Node {
   int data;
   Node* parent = nullptr;
}

Where each node has at most one parent but can have many children. I am trying to find the lowest common ancestor of two nodes (node1 and node2) who do not have any children.

This is my current code:

std::vector<Node*> ancestors1;
std::vector<Node*> ancestors2;
temp_node = node1->parent;
while(temp_node!=nullptr) {
    ancestors1.push_back(temp_node);
    temp_node = temp_node->parent;
}
temp_node = node2->parent;
while(temp_node!=nullptr) {
    ancestors2.push_back(temp_node);
    temp_node = temp_node->parent;
}
Node* common_ancestor = nullptr;
if (ancestors1.size() < ancestors2.size()) {
    ptrdiff_t t = ancestors1.end() - ancestors1.begin();
    std::vector<Node*>::iterator it1 = ancestors1.begin();
    std::vector<Node*>::iterator it2 = ancestors2.end() - t;
    while(it1!=ancestors1.end()) {
        if (*it1 == *it2) {
            common_ancestor = *it1;
        }
        ++it1;
    }
} else {
    ptrdiff_t t = ancestors2.end() - ancestors2.begin();
    std::vector<Node*>::iterator it2 = ancestors2.begin();
    std::vector<Node*>::iterator it1 = ancestors1.end() - t;
    while(it2!=ancestors2.end()) {
        if (*it1 == *it2) {
            common_ancestor = *it1;
        }
        ++it2;
    }
}
return common_ancestor

This code doesn't always work and I'm not sure why.

Please try to create the smallest and simplest tree that "doesn't always work", and use a debugger to step through the code to help figure out what the problem might be. — Some programmer dude
Create function to list ancestrors instead of repeating logic. You have typo btw, as you put node2's ancestros in ancestors1 — Jarod42
Only one iterator moves, so you only check for one ancestror. — Jarod42
just do ++it1; ++it2; in both the sides of if-else blocks. — v78
it2 = ancestors2.end() - t - why? both paths must start from root. Couldn't you just iterate both paths from the start and break out as soon as they differ? — 500 - Internal Server Error

Scheff's Cat Scheff's Cat · Accepted Answer · 2020-03-30T10:18:16

Sorry, I couldn't resist.

Aside from the typos and bugs, I believe it can look even simpler:

#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

struct Node {
  int data;
  Node *parent = nullptr;
};

Node* findCommonAncestor(Node *pNode1, Node *pNode2)
{
  // find paths of pNode1 and pNode2
  std::vector<Node*> path1, path2;
  for (; pNode1; pNode1 = pNode1->parent) path1.push_back(pNode1);
  for (; pNode2; pNode2 = pNode2->parent) path2.push_back(pNode2);
  // revert paths to make indexing simple
  std::reverse(path1.begin(), path1.end());
  std::reverse(path2.begin(), path2.end());
  // compare paths
  Node *pNode = nullptr; // ancestor
  size_t n = std::min(path1.size(), path2.size());
  for (size_t i = 0; i < n; ++i) {
    if (path1[i] == path2[i]) pNode = path1[i];
    else break;
  }
  // done
  return pNode;
}

int main()
{
  // sample tree:
  /*     1
   *     |
   *     2
   *    / \
   *   3   4
   *       |
   *       5
   */
  Node node1 = { 1, nullptr };
  Node node2 = { 2, &node1 };
  Node node3 = { 3, &node2 };
  Node node4 = { 4, &node2 };
  Node node5 = { 5, &node4 };
  Node *pNode = findCommonAncestor(&node3, &node5);
  if (pNode) {
    std::cout << "Lowest common ancestor: " << pNode->data << '\n';
  } else {
    std::cout << "No common ancestor found!\n";
  }
}

Output:

Lowest common ancestor: 2

Live Demo on coliru

Note:

While usage of iterators helps to keep code general…

I would consider this one of the cases where sticking to plain old array (aka std::vector) indexing simplifies things.

Lowest common ancestor of two leaves in a tree

3 Answers