Alipuut

Tehtäväsi on muodostaa lista, joka sisältää puun solmujen alipuiden koot pienimmästä suurimpaan.

Esimerkiksi alla olevassa puussa listan haluttu sisältö on $[1, 1, 1, 1, 2, 3, 7]$. Puussa on neljä lehteä, joissa alipuun koko on $1$. Solmun $2$ alipuun koko on $2$, solmun $4$ alipuun koko on $3$ ja solmun $1$ alipuun koko on $7$.

Toteuta tiedostoon subtrees.py funktio count_subtrees, jolle annetaan parametrina viittaus puun juurisolmuun. Funktio palauttaa listana solmujen alipuiden koot.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children else []

    def __repr__(self):
        if self.children == []:
            return f"Node({self.value})"
        else:
            return f"Node({self.value}, {self.children})"

def count_subtrees(node):
    # TODO

if __name__ == "__main__":
    tree1 = Node(1, [Node(4, [Node(3), Node(7)]),
                     Node(5),
                     Node(2, [Node(6)])])
    print(count_subtrees(tree1)) # [1, 1, 1, 1, 2, 3, 7]

    tree2 = Node(1, [Node(2, [Node(3, [Node(4)])])])
    print(count_subtrees(tree2)) # [1, 2, 3, 4]

    tree3 = Node(1, [Node(2), Node(3), Node(4)])
    print(count_subtrees(tree3)) # [1, 1, 1, 4]