Alipuut

Tehtäväsi on laskea suurin ero vasemman ja oikean alipuun solmujen määrässä jossain binääripuun solmussa. Voit olettaa, että puussa on enintään 100 solmua.

Tehtäväpohjassa esimerkkinä on seuraava puu:

Tässä puussa suurin ero on juuressa: vasemmalla on 0 solmua ja oikealla on 3 solmua, joten ero on 3.

Toteuta tiedostoon subtrees.py funktio diff, joka palauttaa suurimman eron.

from collections import namedtuple

def diff(node):
    # TODO

if __name__ == "__main__":
    Node = namedtuple("Node", ["left", "right"])
    tree = Node(None,Node(Node(None,None),Node(None,None)))
    print(diff(tree)) # 3