package bench;

// ref from: https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-java-3.html
public class binarytrees {
	static class TreeNode {
		int dummy;
		TreeNode left, right;
	}

	static TreeNode createTree(int depth) {
		TreeNode node = new TreeNode();
		if (depth > 0) {
			depth--;
			node.left = createTree(depth);
			node.right = createTree(depth);
		}
		return node;
	}

	static int checkTree(TreeNode node) {
		return node.left == null ? 1 : checkTree(node.left) + checkTree(node.right) + 1;
	}

	public static void main(String[] args) {
		int maxDepth = Integer.parseInt(args[0]), stretchDepth = maxDepth + 1;
		System.out.println("stretch tree of depth " + stretchDepth + "\t check: " + checkTree(createTree(stretchDepth)));
		TreeNode longLastingNode = createTree(maxDepth);
		int depth = 4;
		do {
			int iterations = 16 << (maxDepth - depth), check = 0, item = 0;
			do {
				check += checkTree(createTree(depth));
				item++;
			} while (item < iterations);
			System.out.println(iterations + "\t trees of depth " + depth + "\t check: " + check);
			depth += 2;
		} while (depth <= maxDepth);
		System.out.println("long lived tree of depth " + maxDepth + "\t check: " + checkTree(longLastingNode));
	}
}