locating lowest common ancestor in AVL tree

Question

I have an AVL tree and 2 keys in it. how do I find the lowest common ancestor (by lowest I mean hight, not value) with O(logn) complexity? I've seen an answer here on stackoverflow, but I admit I didn't exactly understand it. it involved finding the routes from each key to the root and then comparing them. I'm not sure how this meets the complexity requirements

Answer 1

For the first node you move up and mark the nodes. For the second node you move up and look if a node on the path is marked. As soon as you find a marked node you can stop. (And remove the marks by doing the first path again).

If you cannot mark nodes in the tree directly then modify the values contained to include a place where you can mark. If you cannot do this either then add a hashmap that stores which nodes are marked.

This is O(logn) because the tree is O(logn) deep and at worst you walk 3 times to the root.

Also, if you wish you can alternate steps of the two paths instead of first walking the first path completely. (Note that then both paths have to check for marks.) This might be better if you expect the two nodes to have their ancestor somewhat locally. The asymptotic runtime is the same as above.

Answer 2

A better solution for the AVL tree (balanced binary search tree) is (I have used C pointers like notation)-

1. Let K1 and K2 be 2 keys, for which LCA is to be found. Assume K1 < K2
2. A pointer P = root of tree
3. If P->key >= K1 and P->key <= K2 : return P
4. Else if P->key > K1 and P->key > K2 : P = P->left
5. Else P = P->right
6. Repeat step 3 to 5

The returned P points to the required LCA.

Note that this approach works only for BST, not any other Binary tree.