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