The Computer Language
Benchmarks Game

binary-trees TypeScript #2 program

source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/
   contributed by Isaac Gouy 
   *reset*
*/


/// <reference path="./Include/node/index.d.ts" />

class TreeNode {
   constructor(
      private left: TreeNode, 
      private right: TreeNode, 
   ) { }

   check(): number {
      if (this.left) {
         return 1 + this.left.check() + this.right.check()
      }
      else {
         return 1
      }
   }
}

function bottomUpTree(depth: number): TreeNode {
   if (depth > 0) {
      // "new TreeNode(" must be on same line as "return" 
      return new TreeNode(
         bottomUpTree(depth-1),
         bottomUpTree(depth-1)
      )
   }
   else {
      return new TreeNode(undefined,undefined)
   }
}


const n = +process.argv[2]
const minDepth = 4
const maxDepth = Math.max(minDepth + 2, n);
const stretchDepth = maxDepth + 1

let check = bottomUpTree(stretchDepth).check()
console.log("stretch tree of depth " + stretchDepth + "\t check: " + check)

const longLivedTree = bottomUpTree(maxDepth)
for (let depth=minDepth; depth<=maxDepth; depth+=2) {
   let iterations = 1 << (maxDepth - depth + minDepth)

   check = 0;
   for (let i=1; i<=iterations; i++) {
      check += bottomUpTree(depth).check()
   }
   console.log(iterations + "\t trees of depth " + depth + "\t check: " + check)
}
console.log("long lived tree of depth " + maxDepth + "\t check: " + longLivedTree.check())

    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Version 2.2.9
node.js v7.9.0


Sat, 15 Apr 2017 00:22:39 GMT

MAKE:
mv binarytrees.typescript-2.typescript binarytrees.typescript-2.ts
/usr/local/src/node-v7.9.0-linux-x64/bin/tsc --alwaysStrict -t ESNEXT  binarytrees.typescript-2.ts
1.53s to complete and log all make actions

COMMAND LINE:
/usr/local/src/node-v7.9.0-linux-x64/bin/node --use_strict binarytrees.typescript-2.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