Puun tyhjennys

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

Tarkastellaan esimerkkinä tehtäväpohjassa olevaa puuta:

Tässä vastaus on $8$, koska mahdolliset poistotavat ovat $[2,4,5,3,1]$, $[2,5,4,3,1]$, $[4,2,5,3,1]$, $[4,5,2,3,1]$, $[4,5,3,2,1]$, $[5,2,4,3,1]$, $[5,4,2,3,1]$ ja $[5,4,3,2,1]$.

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(Node(None,None),Node(Node(None,None),Node(None,None)))
    print(count(tree)) # 8

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(new Node(null,null),
                             new Node(new Node(null,null),
                                      new Node(null,null)));
        System.out.println(c.count(tree)); // 8
    }
}