3.3.2. Lowest Common Ancestor

With Parent Link

Node *LCA(Node *n1, Node *n2) {
    set <Node*> ancestors;
    while (n1 != NULL) {
        ancestors.insert(n1);
        n1 = n1->parent;
    }
    while (n2 != NULL) {
        if (ancestors.count(n2))
            return n2;
        n2 = n2->parent;
    }
    return NULL;
}

Without Parent Link

int depth(Node *node) {
    int d = -1;
    while (node) {
        ++d, node = node->parent;
    }
    return d;
}

Node *LCA(Node *n1, Node *n2) {
    int d1 = depth(n1), d2 = depth(n2);
    if (d1 < d2) {
        swap(n1, n2), swap(d1, d2);
    }
    while (d1 != d2) {
        d2++;
        n1 = n1->parent;
    }

    while (1) {
        if (n1 == n2) return n1;
        n1 = n1->parent, n2 = n2->parent;
    }
    return NULL;
}