binary-trees Node.js program
source code
/* The Computer Language Benchmarks Game
http://benchmarksgame.alioth.debian.org/
contributed by Isaac Gouy
*reset*
*/
function TreeNode(left,right,item){
this.left = left;
this.right = right;
}
TreeNode.prototype.itemCheck = function(){
if (this.left==null) return 1;
else return 1 + this.left.itemCheck() + this.right.itemCheck();
}
function bottomUpTree(depth){
if (depth>0){
return new TreeNode(
bottomUpTree(depth-1)
,bottomUpTree(depth-1)
);
}
else {
return new TreeNode(null,null);
}
}
var minDepth = 4;
var n = +process.argv[2];
var maxDepth = Math.max(minDepth + 2, n);
var stretchDepth = maxDepth + 1;
var check = bottomUpTree(stretchDepth).itemCheck();
console.log("stretch tree of depth " + stretchDepth + "\t check: " + check);
var longLivedTree = bottomUpTree(maxDepth);
for (var depth=minDepth; depth<=maxDepth; depth+=2){
var iterations = 1 << (maxDepth - depth + minDepth);
check = 0;
for (var i=1; i<=iterations; i++){
check += bottomUpTree(depth).itemCheck();
}
console.log(iterations + "\t trees of depth " + depth + "\t check: " + check);
}
console.log("long lived tree of depth " + maxDepth + "\t check: "
+ longLivedTree.itemCheck());
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
v9.4.0
Wed, 10 Jan 2018 18:43:24 GMT
MAKE:
cp -L binarytrees.node binarytrees.js
0.03s to complete and log all make actions
COMMAND LINE:
/opt/src/node-v9.4.0-linux-x64/bin/node binarytrees.js 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303