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())
The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.)

A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers:


Compute the height of both target nodes.
Until the heights are equal, replace the deeper node with its parent.
Until the two nodes are the same, replace both nodes with their respective parent.


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)$.