import java.util.ArrayList;
import java.util.List;

class TreeStats {
	public static void printStats(BinTree tree) {

		// Nodes for each depth
		System.out.println("Num nodes for each depth:");
		int[] depths = new int[height(tree.first) + 1];
		numForDepth(tree.first, depths);
		for (int i = 0; i < depths.length; ++i) {
			System.out.println("\tDepth "+i+": "+depths[i]);
		}

		// Height
		System.out.println("Tree height: "+height(tree.first));

		// Average depth
		System.out.printf("Average depth: %.2f\n",
			(totalDepth(tree.first) / (double)numNodes(tree.first)));

		// First and last word
		System.out.println("First word: "+tree.findSmallest());
		System.out.println("Last word: "+tree.findBiggest());
	}

	public static int height(BinTree.Node node) {
		if (node.left == null && node.right == null)
			return 0;
		else if (node.left != null && node.right == null)
			return height(node.left) + 1;
		else if (node.left == null && node.right != null)
			return height(node.right) + 1;
		else {
			int lh = height(node.left);
			int rh = height(node.right);

			return (lh > rh ? lh : rh) + 1;
		}
	}

	public static int numNodes(BinTree.Node node) {
		if (node == null)
			return 0;

		return 1 + numNodes(node.left) + numNodes(node.right);
	}

	public static int totalDepth(BinTree.Node node) {
		if (node == null)
			return 0;

		return node.depth() + totalDepth(node.left) + totalDepth(node.right);
	}

	public static void numForDepth(BinTree.Node node, int[] acc) {
		if (node == null)
			return;

		acc[node.depth()] = acc[node.depth()] + 1;

		numForDepth(node.left, acc);
		numForDepth(node.right, acc);
	}
}