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$.

Python

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

Java

Toteuta tiedostoon Subtrees.java metodi diff, joka palauttaa suurimman eron.

public class Subtrees {
    public int diff(Node node) {
        // TODO
    }

    public static void main(String[] args) {
        Subtrees s = new Subtrees();
        Node tree = new Node(null,
                             new Node(new Node(null,null),
                                      new Node(null,null)));
        System.out.println(s.diff(tree)); // 3
    }
}