/*
bintrees.d, D code by leonardo maffi, V.1.0 Apr 20 2008

D language implementation of few solutions to the "Binary Trees" problems by
Nick Parlante, see http://cslibrary.stanford.edu/

In Python you may implement a node as the list [data, left, right] and None for
empty trees (you may define a Node class too).

In D too there are many ways to implement such solutions, using std.boxer to simulate
the same solutions used in Python, or using a struct node, or using the Java class
solutions shown in the "Binary Trees" document. Here I have chosen the shorter and
simpler implementation, the nodes are objects (in D they are always used by reference),
but I have used free functions, avoiding the need of extra complexity necessary
for the OOP Java solutions. The Python solutions can be quite similar.
*/

import std.string: format;

// My D libs: www.fantascienza.net/leonardo/so/libs_d.zip
import d.func: putr, filter, xrange, autoAssign;

class T {
    int data;
    T left, right;
    this(typeof(data) data, T left, T right) { mixin(autoAssign("data left right")); }
    static T opCall(typeof(data) data, T left, T right) { return new T(data, left, right); }
    string toString() { return format("<%s, %s, %s>", data, left, right); }
}

bool hasPathSum(T t, typeof(T.init.data) tot, typeof(T.init.data) subtot=0) {
    if (t is null)
        return false;
    subtot += t.data;
    if (t.left is null && t.right is null)
        return tot == subtot;
    return hasPathSum(t.left, tot, subtot) || hasPathSum(t.right, tot, subtot);
}

void printPaths(T t, typeof(T.init.data)[] path=null) {
    if (t is null)
        return;
    if (path is null)
        path = [];
    auto path2 = path ~ t.data;
    if (t.left is null && t.right is null)
        putr(path2);
    else {
        printPaths(t.left, path2);
        printPaths(t.right, path2);
    }
}

T mirror(T t) {
    return t is null ? t : T(t.data, mirror(t.right), mirror(t.left));
}

T inplaceMirror(T t) {
    if (t !is null) {
        auto auxt = inplaceMirror(t.left);
        t.left = inplaceMirror(t.right);
        t.right = auxt;
    }
    return t;
}

bool areEqual(T t1, T t2) {
    if (t1 is null && t2 is null)
        return true;
    if (t1 is null || t2 is null)
        return false;
    return t1.data == t2.data && areEqual(t1.left, t2.left) && areEqual(t1.right, t2.right);
}

void main() {
    T N;
    T tree = T(1, T(2, T(3, T(4, N, N), T(5, N, N) ), N),
                  T(6, T(7, N, N), T(8, N, T(9, N, N))));

    putr(tree);
    // <1, <2, <3, <4, null, null>, <5, null, null>>, null>, <6, <7, null, null>, <8, null, <9, null, null>>>>

    putr( filter((int i){return hasPathSum(tree, i);}, xrange(100)) );
    // [10, 11, 14, 24]

    printPaths(tree);
    // [1, 2, 3, 4]
    // [1, 2, 3, 5]
    // [1, 6, 7]
    // [1, 6, 8, 9]

    putr(mirror(tree));
    // <1, <6, <8, <9, null, null>, null>, <7, null, null>>, <2, null, <3, <5, null, null>, <4, null, null>>>>

    putr(inplaceMirror(tree));
    // <1, <6, <8, <9, null, null>, null>, <7, null, null>>, <2, null, <3, <5, null, null>, <4, null, null>>>>

    auto t1 = T(1, T(2, N, N), T(3, N, N));
    auto t2 = T(1, T(2, N, N), T(3, N, N));
    assert(areEqual(t1, t2));

    auto t3 = T(1, T(2, N, N), T(4, N, N));
    assert(!areEqual(t1, t3));

    auto t4 = T(1, T(2, N, N), N);
    assert(!areEqual(t1, t4));

    auto t5 = T(1, T(2, N, N), T(3, T(4, N, N), T(5, N, N)));
    auto t6 = T(1, T(2, N, N), T(3, T(4, N, N), T(5, N, N)));
    assert(areEqual(t5, t6));
}