Lowest Common ancestor in a Binary Search Tree

Its pretty easy to find closest common ancestor in a BST if all the elements are distinct. But what if some of the values are same. Till now we were just comparing the data of nodes and that wa开发者_开发知识库s it, but now do we need to check for nodes' address instead of just values?

Yes, instead of using just your key for the comparison, use (key, address of node) for comparison. This simplifies the code when dealing with non-unique keys.

Without seeing what kind of struct you are using, it's hard to give specifics, but you could try something like this pseudocode:

struct BST {
    struct BST* parent;
    struct BST* left;
    struct BST* right;
    void* value;
}

find_common_ancestor(struct BST* x, struct BST* y)
{
    set<struct BST*> ancestors;

    // Add all of x's ancestors to set.
    while (true) {
        ancestors.insert(x);

        if (x == NULL)
            break;

        x = x=>parent;
    }

    // Check y's ancestors against x's until a match is found.
    while (true) {
        if (ancestors.count(y) > 0)
            return y;

        y = y->parent;
    }
}

here is psudocode. just convert them into syntax.

GETLeastCommonAn(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF