Is there a better way to find the lowest common ancestor?

Question

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

Please prove that I'm wrong!

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

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

You can 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 simple, and the worst case is O (n), the middle case is probably O (logn), especially if the tree is balanced (where n is the number of nodes in the tree).

Answer 1

, , . , ; , , node .

, . , , n- ; , , . , , ( ). , , node.

Answer 2

, . . BST:

10
  \
   \
   15
  /  \
 14  16

you'r 10 .

, , , , node, , 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 root node
    //node1 and node2 are nodes whose ancestor is to be located


}