Difference between revisions of "TADM2E 5.19"
From Algorithm Wiki
(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...") |
(Undo revision 808 by Hdyldhdlgzos (talk)) |
| (One intermediate revision by one other user not shown) | |
(No difference)
| |
Latest revision as of 15:58, 23 July 2020
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 $ O(n) $ time
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()
