CSES - Puun tyhjennys Binääripuusta poistetaan joka askeleella jokin lehti, kunnes puu on tyhjä. Monellako tavalla poistot voi toteuttaa?

Voit olettaa, että puussa on korkeintaan 100 solmua ja että vastaus on aina korkeintaan $10^{18}$.

Python

Toteuta tiedostoon cleartree.py funktio count(root), joka antaa poistotapojen määrän.
from collections import namedtuple

def count(node):
    # TODO

if __name__ == "__main__":
    Node = namedtuple("Node",["left","right"])
    tree = Node(None,Node(Node(None,None),Node(None,None)))
    print(count(tree)) # 2
Java

Toteuta tiedostoon ClearTree.java metodi count, joka antaa poistotapojen määrän.
public class ClearTree {
    public long count(Node node) {
        // TODO
    }

    public static void main(String[] args) {
        ClearTree c = new ClearTree();
        Node tree = new Node(null,
                             new Node(new Node(null,null),
                                      new Node(null,null)));
        System.out.println(c.count(tree)); // 2
    }
}