Here is given code:

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; }

public void insert(int id){

}

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

public static void main(String arg[]){

} }

--------------------------- NODE

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

1. BST, 40 pts 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 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 B 100000, n 1million. For each n you will pick uniformly random keys in the range I-2 31 -1]. For each n repeat the experiment 31 several time and calculate the average height of the tree for each n. d Compare the average height to log2 n for each n Calculate constants that relate the average height to log2 n for each n. Is there any rela- tionship betweens constants for each n