**part c**

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.key) {

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 Integer search_Next(Integer k)

{

if(root == null)

return null;

else

{

Node current = root;

while(current != null)

{

if(current.key == k) //found a matching key

{

//now go to the left most node in the right subtree

if(current.right == null) //there is right subtree?

return null;

else

{

current = current.right;

while(current.left != null) //no more left node?

{

current = current.left;

}

return current.key;

}

}

else if(k < current.key)

current = current.left;

else

current = current.right;

}

return null;//if no matching key was found

}

}

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();

System.out.println(“nsearch_Next(2) = “+bst.search_Next(2));

}

}

**output**

1 2 4 5 7

search_Next(2) = 4

**part D**

package BST;

import java.util.Random;

public class CompareHeights {

private static void generateAndCompare(int nodeSize)

{

Random numRandom=new Random();

Random signRandom = new Random();

BinarySearchTree bst = new BinarySearchTree();

int num,sign;

System.out.println(“Generating tree with “+nodeSize +” nodes”);

for(int i = 0; i < nodeSize; i++)

{

sign = signRandom.nextInt(2);

num = numRandom.nextInt(Integer.MAX_VALUE);

if(sign == 0)//whenever sign is 0 , make the number -ve

num = -num;

bst.insert(num);

}

System.out.println(“Generated tree , its height is “+bst.height());

double h = Math.log(nodeSize + 1 ) / Math.log(2); //calculating log base 2

System.out.println(“Expected minimum height of tree is log (” + (nodeSize+1) + “) = ” + h);

System.out.println(“—————“);

}

public static void main(String[] args) {

int n[] = {10, 100, 500, 1000, 2000, 5000, 10000, 100000, 1000000};

for(int i = 0; i<n.length; i++)

{

generateAndCompare(n[i]);

}

}

}

**output**

Generating tree with 10 nodes

Generated tree , its height is 6.0

Expected minimum height of tree is log (11) = 3.4594316186372978

—————

Generating tree with 100 nodes

Generated tree , its height is 13.0

Expected minimum height of tree is log (101) = 6.6582114827517955

—————

Generating tree with 500 nodes

Generated tree , its height is 20.0

Expected minimum height of tree is log (501) = 8.968666793195208

—————

Generating tree with 1000 nodes

Generated tree , its height is 19.0

Expected minimum height of tree is log (1001) = 9.967226258835993

—————

Generating tree with 2000 nodes

Generated tree , its height is 24.0

Expected minimum height of tree is log (2001) = 10.966505451905741

—————

Generating tree with 5000 nodes

Generated tree , its height is 30.0

Expected minimum height of tree is log (5001) = 12.288000889707574

—————

Generating tree with 10000 nodes

Generated tree , its height is 30.0

Expected minimum height of tree is log (10001) = 13.287856641840545

—————

Generating tree with 100000 nodes

Generated tree , its height is 39.0

Expected minimum height of tree is log (100001) = 16.60965490131509

—————

Generating tree with 1000000 nodes

Generated tree , its height is 47.0

Expected minimum height of tree is log (1000001) = 19.931570012018494

—————

**part E**

The minimum height of a BST with n nodes is log (n+1). So we see from the output above that the height of generated tree is atleast as much as log(n+1)