Is there a better way to find lowest common ancestor?

Question

I know similar questions have been asked before, but I think my solution is far simpler. Especially compared to Wikipedia.

Please prove me wrong!

If you have a tree with nodes that have the given data structure:

struct node
{
    node * left;
    node * right;
    node * parent;
    int key;
}

You could write a function like this:

node* LCA(node* m, node* n)
{
    // determine which of the nodes is the leftmost
    node* left = null;
    node* right = null;
    if (m->key < n->key)
    {
        left = m;
        right = n;
    }
    else
    {
        left = n;
        right = m;
    }
    // start at the leftmost of the two nodes,
    // keep moving up the tree until the parent is greater than the right key
    while (left->parent && left->parent->key < right->key)
    {
        left = left->parent;
    }
    return left;
}

This code is pretty straightforward and worst case is O(n), average case it is probably O(logn), especially if the tree is balanced (where n is the number of nodes in the tree).

Answer 1

Your Algorithm looks okay to me, at least I couldn't think of anything better. Note that you don't need the parent pointer; instead you can go down the tree starting from the root, and find the first node whose key lays between the two initial keys.

However, your problem has nothing to do with the one Tarjan solved. First of all, you consider binary trees and he considers n-ary trees; but this is probably a detail. More importantly, you consider search trees, while Tarjan considers general trees (no ordering on the keys). Your problem is much simpler, because, depending on the key, you can guess where a certain node has to be in the tree.

Answer 2

No, I am sorry. But your algorithm isn't good. take the following BST:

10
  \
   \
   15
  /  \
 14  16

you'r algorithm will return 10 as the lowest common ancestor.

Thus, you could write algorithm that take, say, the left node and than go to its parent and run in-order on it and that check if right was in the output of the in-order

Answer 3

Node* getAncestor( Node* root, Node* node1 , Node* node2 )
{
    if( root->val > node1->val && root->val > node2->val )
        getAncestor( root->left , node1 , node2 );
    //recursive call with left subtree

    if( root->val < node1->val && root->val < node2->val )
        getAncestor( root->right , node1 , node2 );
    //recursive call with right subtree

    return root ;
    //returning the root node as ancestor

    //initial call is made with the tree's root node
    //node1 and node2 are nodes whose ancestor is to be located


}