0
$\begingroup$

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())
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Oct 6 at 17:54
  • 1
    $\begingroup$ Any common ancestor? So you can always return the root? $\endgroup$ – md5 Oct 6 at 19:21
  • 1
    $\begingroup$ 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 $\endgroup$ – md5 Oct 6 at 19:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Oct 6 at 19:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Oct 6 at 19:36
0
$\begingroup$

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:

  1. Compute the height of both target nodes.
  2. Until the heights are equal, replace the deeper node with its parent.
  3. 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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.