Difference between revisions of "TADM2E 5.19"

From Algorithm Wiki
Jump to: navigation, search
(Created page with " for any node in the tree, there are two possibilities # either the diameter is contained in one of the subtrees # or the node itself is at the top of the longest path in the...")
 
(Blanked the page)
Line 1: Line 1:
  
for any node in the tree, there are two possibilities
 
# either the diameter is contained in one of the subtrees
 
# or the node itself is at the top of the longest path in the tree that defines the diameter
 
 
in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node
 
 
the following algorithm calculates the diameter in <math>O(n)</math> time
 
 
<source lang="python">
 
 
class Node:
 
 
    def __init__(self, value, children):
 
        self.value = value
 
        self.children = children
 
 
    @classmethod
 
    def preorder(cls, lists):
 
        return cls(
 
                lists[0],
 
                [cls.preorder(l) for l in lists[1:]]
 
            )
 
 
 
def dd(root):
 
    """
 
    returns depth, diameter for tree with given root node
 
 
    >>> dd(Node.preorder([0, [1], [2]]))
 
    (1, 2)
 
    >>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
 
    (2, 4)
 
    >>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
 
    (4, 5)
 
    """
 
    d1 = d2 = -1
 
    md = 0
 
    for child in root.children:
 
        depth, diameter = dd(child)
 
        if diameter > md:
 
            md = diameter
 
        if depth >= d1:
 
            d2 = d1
 
            d1 = depth
 
        elif depth > d2:
 
            d2 = depth
 
    return d1 + 1, max(md, d1 + d2 + 2)
 
 
 
if __name__ == "__main__":
 
    import doctest
 
    doctest.testmod()
 
 
</source>
 

Revision as of 06:28, 16 July 2020