# Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using.

# in class Scene
@staticmethod
def common_ancestor(item1, item2):
if item1 is item2:
return item1
com = Scene.common_ancestor(item1.parentItem(), item2)
if com is None:
com = Scene.common_ancestor(item1, item2.parentItem())
return com


Anyway, confusion sets in quickly with this one. Any ideas how to proceed logically?

Steven's idea in the comments:

# in class Scene
@staticmethod
def is_ancestor_of(anc, item):
if anc is None:
return True
if item is None:
return False
if item is anc:
return True
return Scene.is_ancestor_of(anc, item.parentItem())

@staticmethod
def common_ancestor(item1, item2):
if Scene.is_ancestor_of(item1, item2):
return item1
if Scene.is_ancestor_of(item2, item1):
return item2
return Scene.common_ancestor(item1.parentItem(), item2.parentItem())

• I don't know what a vernacular is in this context, but the above snippet of code does not seem to compute the LCA of item1 and item2. Also, I'd suggest writing the algorithm in pseudocode or adding a description its intended operation. – Steven Oct 6 '19 at 17:54
• Any common ancestor? So you can always return the root? – md5 Oct 6 '19 at 19:21
• So it's called the lowest common ancestor, and it always exists in a tree. It depends how naively you allow yourself to compute it, but you'll probably need to precompute some more information in any case. Btw your last line is quite mysterious to me – md5 Oct 6 '19 at 19:30
• Are you able to quickly tell if a node $u$ is an ancestor of a node $v$? If so and one node is an ancestor of the other, return it. Otherwise recurse on the nodes' parents. – Steven Oct 6 '19 at 19:34
• The naive version is just to traverse the path from the first vertex to the root and mark/store the encountered vertices. Then traverse the path from the second vertex to the root and return the first marked/stored vertex. – Steven Oct 6 '19 at 19:36

A (non-recursive) $$O(n)$$ time and $$O(1)$$ space algorithm, assuming that nodes have parent pointers:
The time complexity of this solution is actually $$O(h)$$ where $$h$$ is the maximum height of the tree; by the same token, the time complexity of the solution in the question is $$O(h)^2$$. If the tree is known to be (somewhat) balanced, then $$h = O(\log n)$$. Even so, $$O(\log n)$$ is probably better than $$O((\log n)^2)$$.