problem in finding a common ancestor for two nodes

Question

I have the following code for finding the common ancestor of two nodes in a binary search tree. If the code can find the nth common ancestor that common ancestor will be returned and if there is no common ancestor (-1) will be returned. Logically the code seems to be correct but there is an error in code development that I can not find that. Is there any body to help?

I have added the binary search tree image that is not displayed!!!

Answer 1

The comparison and condition commonParent->data != n is comparing apples with oranges, i.e. data with a count. They are unrelated. You cannot expect commonParent to somehow walk n-1 steps upwards with this. It is already too late for that -- commonParent is the node for when n is 1, but for other values of n you need to go up the tree.

I would suggest to first count the number of nodes that are common ancestors of b and c, then check if n is less than or equal to that, and if so, to traverse the tree again to find the corresponding node.

Code:

int countCommonAncestors(Node* root, int c, int b) {
    int count = 0;
    while (root != nullptr) {
        count++;
        if (root->data > c && root->data > b) {
            root = root->left;
        } else if (root->data < c && root->data < b) {
            root = root->right;
        } else {
            break;
        }
    }
    return count;
}

int getDataOnPath(Node* root, int b, int level) {
    while (level-- > 0) {
        root = root->data > b ? root->left : root->right;
    }
    return root->data;
}

In your main you can then do:

    int count = countCommonAncestors(root, c, b);
    int result = count < n ? -1 : getDataOnPath(root, b, count - n);
    cout << result << endl;