0

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

littlerunaway
  • 443
  • 2
  • 8
  • 18

2 Answers2

0

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.

Bernd Elkemann
  • 23,242
  • 4
  • 37
  • 66
  • Why mark at all? Just walk up, reverse the paths, and walk back on both paths simultaneously until they split. – Vincent van der Weele May 14 '14 at 09:27
  • That is is possible too and you should add it as an answer. I did not even think of it because it needs dynamic memory (or a clever implementation) to build the lists. – Bernd Elkemann May 14 '14 at 09:30
  • Also it can not use the possible locality (like the alternating version does). But his algorithm has other advantages i think, he should add it as an answer. – Bernd Elkemann May 14 '14 at 09:45
  • Actually it can be done in constant memory. Just do a standard tree traversal. When the two keys are found in different subtrees of the current node, you have found the LCA – Niklas B. May 14 '14 at 10:10
0

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.

Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80