gistfile1.js

// a tree
var t = {
    left: {
        left: {
            left: null,
            right: null            
        },
        right: null
    },
    right: {
        left: null,
        right: null
    }
};

// v1: recursive
var depth = function(t) {
    if (t == null) {
        return 0;
    } else {
        return 1 + Math.max(depth(t.left), depth(t.right));
    }
};
depth(t);

// v2: cps, still recursive
var id = function(x) {
    return x;
};
var depth_cps = function(t, k) {
    if (t == null) {
        return k(0);
    } else {
        return depth_cps(t.left, function(r1) {
            return depth_cps(t.right, function(r2) {
                return k(1 + Math.max(r1, r2));
            });
        });
    }    
};
depth_cps(t, id);

// v3: trampolining, non recursive
var depth_cps2 = function(t, k) {
    if (t == null) {
        return k(0);
    } else {
        return function() {
            return depth_cps2(t.left, function(r1) {
                return function() {
                    return depth_cps2(t.right, function(r2) {
                        return k(1 + Math.max(r1, r2));
                    });
                };
            });
        };
    }    
};
var depth_trampoline = function(t) {
    var bounce = depth_cps2(t, id);
    while (typeof bounce == "function") {
        bounce = bounce();
    }
    return bounce;
}
depth_trampoline(t);

// make a deep tree
var t2 = (function() {
    var r = {};
    var rr = r;
    for (var i = 0; i < 100000; ++i) {
        rr.left = {};
        rr.right = null;
        rr = rr.left;
    }
    rr.left = null;
    return r;
})();
depth(t2);                      // Safari: 'max stack exceeded'
depth(t2, id);                  // as above
depth_trampoline(t2);           // works