I have given you a generic binary tree class BinTree.java. It contains a method, makeRandomTree(int n), that creates a binary tree of a random shape with n nodes. Each node has a "name" consisting of the step at which the node was created (i.e. 0 is the first node created, 1 the second, and so on. The toString method prints the tree in pre-order, including the empty links. This is enough information to re-create the tree on paper so you can see what it looks like. I would like you to 1) write three routines, pre-order, in-order, and post-order which will print the tree in each of those ways, similar to what the toString method does. 2) write a recursive routind depth() which returns the depth of the deepest node in the tree. The root has depth 0. The empty tree has depth --1. 3) Write a main program that asks the user to enter two integers: n, a number of nodes, and howMany. Over and over again, for a total of howMany times, instantiate a new tree with n nodes, find its depth, and ultimately print the depths of the shallowest, average depth, and deepest tree. Sample run: Enter n: 10 Emter repetitions: 1000 Shallowest tree was  Deepest tree was  Average depth was  

GENERIC BINARY TREE GIVEN import java.util.Random; public class BinTree { private Node root; private Random r; public BinTree() { this.root = null; this.r = new Random(); } public void makeRandomTree(int n) { for (int i = 0; i < n; i++) { ranInsert(i); } } public void ranInsert(int name) { Node where = root; Node next = null; boolean done = (where == null); if (root == null) { root = new Node(name); return; } while (!done) { if (r.nextBoolean()) { next = where.getLeft(); if (next == null) { where.setLeft(new Node(name)); done = true; } } else { next = where.getRight(); if (next == null) { where.setRight(new Node(name)); done = true; } } where = next; } } public String toString() { return recToString(this.root, "", 0); } private String recToString(Node r, String soFar, int depth) { String retval = soFar; if (r == null) { retval += "Null "; } else { retval += r.getName() + " "; retval = recToString(r.getLeft(), retval, depth + 1); retval = recToString(r.getRight(), retval, depth + 1); } return retval; } public class Node { private R value; private Node left; private Node right; private int name; public Node(int n, R val, Node lft, Node r) { this.name = n; this.value = val; this.left = lft; this.right = r; } public Node (int n, R val) { this(n, val, null, null); } public Node (int n) { this(n, null, null, null); } public Node () { this(0, null, null, null); } public R getValue() { return this.value; } public int getName() { return this.name; } public Node getLeft() { return this.left; } public Node getRight() { return this.right; } public void setLeft(Node lft) { this.left = lft; } public void setRight(Node r) { this.right = r; } } public static void main(String args[]) { BinTree bt = new BinTree(); bt.makeRandomTree(Integer.parseInt(args[0])); System.out.println(bt); } }