Please respond the correct questions. Explicitly I want answers fro c, d, e !!!

Here is my code for a and b !

package BST;

public class BinarySearchTree { public static Node root;

public BinarySearchTree() { // Constructor this.root = null; }

public boolean search(int id) { Node current = root; while (current != null) { if (current.key == id) { return true; } else if (current.key > id) { current = current.left; } else { current = current.right; } } return false; }

/** The insert method was added * * @param id integer. */ public void insert(int id) {

Node newNode = new Node(id);

if (root == null) {

root = newNode;

return;

}

Node current = root;

Node parent = null;

while (true) {

parent = current;

if (id

current = current.left;

if (current == null) {

parent.left = newNode;

return;

}

} else {

current = current.right;

if (current == null) {

parent.right = newNode;

return;

}

}

}

}

private int HeightUtil(Node root) {

if (root == null)

return -1;

else

return 1 + Math.max(HeightUtil(root.left), HeightUtil(root.right));

}

public double height() { // Compute the height of Binary Search

return HeightUtil(root);

}

public void InorderTraversal() {

inOrderHelper(root);

}

private void inOrderHelper(Node root) {

if (root != null) {

inOrderHelper(root.left);

System.out.print(root.key + " ");

inOrderHelper(root.right);

}

}

public static void main(String arg[]) {

Integer[] a = { 1, 5, 2, 7, 4 };

BinarySearchTree bst = new BinarySearchTree();

for (Integer n : a)

bst.insert(n);

bst.InorderTraversal();

}

}

Another Node class

package BST; public class Node{ int key; Node left; Node right; public Node(int data){ key = data; left = null; right = null; } }

The purpose of this questions is to observe the behavior of binary search trees when adding random integers. You have already given a code for binary search tree (see zip file BST) a Add the function insert (int id) to the BST class. b Add a function height (Node x) to the BST class. This function will compute the height of a tree rooted at Node x. c Add a function function search Next (int k) to the BST class that find smallest id that is greater than k in the BST. d Let n denote the number of nodes. Construct binary search trees for n = 10, n = 100, n = 500, n = 1000, n = 2000, n = 5000, n = 10000, n = 100000, n = 1million. For each n you will pick uniformly random keys in the range [-2^31, 2^31 - 1]. For each n repeat the experiment several time and calculate the average height of the tree for each n. e Compare the average height to log_2 (n + 1) -1 for each n. Calculate constants that relate the average height to log_2 (n + 1) -1 for each n. Is there any relationship betweens constants for each n