Subtrees

Your task is to compute the largest difference in the number of nodes in the left and right subtree of any node in a given binary tree. You may assume that the tree has at most 100 nodes.

The example in the code template represents the following tree:

Here the largest difference is in the root: 0 nodes on the left and 3 nodes on the right resulting a difference of 3.

In a file subtrees.py, implement a function diff that returns the largest difference.

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