hawstein / cracking-the-coding-interview Goto Github PK

int getHeight(Node *node) {
    int height = 0;
    while (node) {
        height++;
        node = node->parent;
    }
    return height;
}

Node* first_ancestor(Node* n1, Node* n2){
    int height1 = getHeight(n1), height2 = getHeight(n2);
    if (height1 < height2) {
        swap(height1, height2);
        swap(n1, n2);
    }
    int diff = height1 - height2;
    while (diff--)
        n1 = n1->parent;
    while (n1 != n2) {
        n1 = n1->parent;
        n2 = n2->parent;
    }
    return n1;
}