Tree traversal in a customised way in Python?

I have two trees in python. I need to compare them in a customized way according to the following specifications. Suppose I have a tree for entity E1 and a tree for entity E2. I need to traverse both the trees starting from E1 and E2 and moving upwards till I get to a common root. (Please note that I have to st开发者_如何学运维art the traversal from node E1 on the first tree and node E2 on the second tree.) Then I need to compare the count of the lengths of both their paths.

Can someone provide me an insight as to how to do this in Python? Can the classical tree traversal algorithms be useful here?

This is not a "traveral" (which visits each node in a tree); what you describe is merely following the parents.

The algorithm would look as follows. One of the tricks is to interleave calculations, so that the algorithm is guaranteed to terminate quickly. You also have to consider cases like node1==node2. This is also an O(A+B=N) rather than O(A*B=N^2) algorithm, where we consider the distance between the nodes and their youngest common ancestor.

def findYoungestCommonAncestor(node1, node2):
    visited = set()
    if node1==node2:
        return node1
    while True:
        if node1 in visited:
            return node1
        if node2 in visited:
            return node2

        if not node1.parent and not node2.parent:
            return None
        if node1.parent:
            visited.add(node1)
            node1 = node1.parent
        if node2.parent:
            visited.add(node2)
            node2 = node2.parent

The nodes node1 and node2 may be part of a forest (a set of interlinked trees) and this should still work.

More elegant would be something like:

def ancestors(node):
    """
        an iterator of node, node.parent, node.parent.parent...
    """
    yield node
    while node.parent:
        yield node
        node = node.parent

def interleave(*iters):
    """
        interleave(range(3), range(10,16)) -> 0,10,1,11,2,12,13,14,15
    """
    ignore = object()
    for tuple in zip_longest(*iters, fillvalue=ignore):
        for x in tuple:
            if not x is ignore:
                yield x

def findYoungestCommonAncestor(node1, node2):
    # implementation: find first repeated value in interleaved ancestors
    visited = set()
    for node in interleave(ancestors(node1), ancestors(node2)):
        if node in visited:
            return node
        else:
            visited.add(node)

That they are trees is not even relevant to the solution. You're looking for how long it takes for two single-linked (the parent link) lists to converge into the same list. Simply follow the links, but keep a length count for each visited node. Once you reach an already visited node, sum the previously found count and the new one. This won't work if either list ends up circular, but if they do it's not a proper tree anyway. A way to fix that case is to track separate visited dictionaries for either branch; if you reach a node visited in its own branch, you can stop traversing that branch as there's no point recounting the loop.

This all naturally assumes you can find the parent of any node. The simplest tree structures don't actually have that link.

def closest_common_ancestor(ds1, ds2):

        while ds1 != None:
                dd = ds2
                while dd != None:
                        if ds1 == dd:
                                return dd
                        dd = dd.parent
                ds1 = ds1.parent
        return None